Research map / Learning theory and algorithms / Combinatorial and search optimization
Learning-Augmented Algorithms for Online Linear and Semidefinite Programming
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Incorporate fractional advice and confidence-weighted growth into primal-dual updates | Online covering LP · Online covering LP | consistency ratio: O\left(\frac{1}{1-\lambda}\right) | Helped |
| Use guess-and-double phases and primal-dual updates with fractional advice | Online covering LP · Online covering LP | robustness ratio: O\left(\log\frac{\kappa n}{\lambda}\right) | Helped |
| Extend the advice-guided primal-dual framework to matrix constraints | Online covering SDP · Online covering SDP | consistency ratio: O\left(\frac{1}{1-\lambda}\right) | Helped |
| Extend the advice-guided primal-dual framework to matrix constraints | Online covering SDP · Online covering SDP | robustness ratio: O\left(\log\frac{\kappa n}{\lambda}\right) | Helped |
| Add box-constraint handling to the advice-guided primal-dual algorithm | Online covering LP · Online covering LP with box constraints | consistency ratio: O\left(\frac{1}{1-\lambda}\right) | Helped |
| Add box-constraint handling and sparsity-aware robustness analysis | Online covering LP · Online covering LP with box constraints | robustness ratio: O\left(\log\frac{s }{\lambda}\right) | Helped |
| Add box-constraint handling to the advice-guided primal-dual algorithm | Online covering SDP · Online covering SDP with box constraints | consistency ratio: O\left(\frac{1}{1-\lambda}\right) | Helped |
| Add box-constraint handling and sparsity-aware robustness analysis | Online covering SDP · Online covering SDP with box constraints | robustness ratio: O\left(\log\frac{s }{\lambda}\right) | Helped |
| Use fractional rather than integral advice | Learning-augmented online covering algorithms · Online covering LP and SDP | advice representation | Helped |
| Satisfy each arriving violating constraint by a factor of 2 | PDLA · Online covering LP and SDP | number of violating constraints processed | Helped |
| Use continuous rather than discretized primal-dual updates for general coefficients | Online covering LP · Online covering LP | handling arbitrary positive coefficients | Helped |
Closest papers by meaning
- Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems (NeurIPS 2024 · similarity 0.86)
- Learning Valid Dual Bounds in Constraint Programming: Boosted Lagrangian Decomposition with Self-Supervised Learning (AAAI 2025 · similarity 0.86)
- Decoupling Learning and Decision-Making: Breaking the $\mathcal{O}(\sqrt{T})$ Barrier in Online Resource Allocation with First-Order Methods (ICML 2024 · similarity 0.85)
- Generalization Guarantees for Learning Score-Based Branch-and-Cut Policies in Integer Programming (NeurIPS 2025 · similarity 0.85)
- Semi-infinite Nonconvex Constrained Min-Max Optimization (NeurIPS 2025 · similarity 0.85)
- Learning Augmented Exact Exponential Algorithms (NeurIPS 2026 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.