Optimization
The Top Open Problems editorial order restricted to Computer Science, followed by cross-listed economics entries. Existing relative order is retained, with provisional placements for new game-learning questions; most entries have no individual difficulty assessment. About rankings
Browse by subject
Search this collection by problem ID, title, classification, subject, provider, or model.
Search results
No matching problems. Try another search or clear a filter.
103 records · Search and filter
- CS-22 NP-Completeness of the Minimum Circuit Size Problem (MCSP)
- CS-37 Polynomial pivot rule for the simplex method
- CS-47 Metric TSP Subtour LP Integrality Gap Conjecture
- CS-62 Polynomial-Time Decidability of Semidefinite Programming Feasibility
- CS-78 Polynomial-Time P-Matrix Linear Complementarity Problem
- CS-80 Deterministic Linear-Time Minimum Spanning Tree Problem
- CS-85 Smale's 9th Problem: Linear Programming in Polynomial Time
- CS-105 10 Lectures and 42 Open Problems — Sum of Squares approximation ratio for Max-Cut
- CS-114 Polynomial Algorithms for Mean-Payoff Games and Linear Programming
- CS-121 Bounded additive gap for the bin-packing configuration LP
- CS-139 Exponential semidefinite complexity for perfect matching
- CS-140 Optimal Max-Cut approximation hardness
- CS-142 Metric k-median at factor one plus two over e
- CS-143 Metric k-median strictly below factor two
- CS-157 Almost-linear maximum-cardinality matching
- CS-165 Polynomial-time three-machine unit-job scheduling
- CS-177 The Polynomial Hirsch Conjecture
- CS-180 10 Lectures and 42 Open Problems — Tightness of the Multireference Alignment SDP
- CS-187 10 Lectures and 42 Open Problems — Maximum and minimum bisections on random regular graphs
- CS-188 10 Lectures and 42 Open Problems — Sharp tightness of the Angular Synchronization SDP
- CS-212 ML degree, feasibility, and a Gaussian likelihood-root trichotomy
- CS-276 Central-Trajectory Integral Bounds
- CS-283 Integral Primal Certificates for Submodular Minimization
- CS-285 Sampling Algorithms for Maximum-Cut Density
- CS-298 Convex-Hull Decomposition for Mixed-Integer Bipartite Systems
- CS-300 Linear Optimization over Mixed-Integer Bipartite Systems
- CS-303 Optimal Feasible Sets from Quantized Trajectory Observations
- CS-319 Efficient Moment Relaxations for Polynomial Optimization
- CS-322 Polynomial-Time Minimization of K-Submodular Functions
- CS-323 Complexity of Maximizing Initial Odd Ears
- CS-324 Additive Integrality Gap for Ring Loading
- CS-325 Exact Integrality Gap for Capacitated Facility Location
- CS-326 Compact Constant-Gap Relaxations for Capacitated Facility Location
- CS-346 Practical Sum-of-Squares Tensor Completion
- CS-348 Global Optimization of Overparameterized Shallow Networks
- CS-349 Extrapolating Clusterings from Semidefinite Subsamples
- CS-350 Local Approximation of Random-Graph Semidefinite Programs
- CS-352 Proximity and Sparsity of Optimal Integer Solutions
- CS-353 Convergence Rates for Convex-Body Bounds
- CS-354 Fast Low-Rank Maximum-Weight Assignment
- CS-355 Integrality Gaps for Directed Linear k-Cut
- CS-356 Hardness of Root-Dependent Spanning-Tree Optimization
- CS-357 Hardness of Path-Cost Arborescence Optimization
- CS-359 Degree-Utility Optimization in Graphs
- CS-363 Geometric Explanations and Polynomial Pivot Rules for Simplex
- CS-364 Sharp Smoothed Complexity of Simplex Pivot Rules
- CS-371 Semidefinite Hierarchies for Equiangular Line Bounds
- CS-374 Minimum Crossing Realizations of Spatial Polygon Angle Sequences
- CS-377 Integer Programming with Bounded Subdeterminants
- CS-379 Arborescences Induced by Linear-Programming Pivot Rules