Optimization
Provisional editorial order for Top Open Problems: Millennium Prize Problems first, followed by assessed difficulty tiers; the unassessed remainder keeps its previous catalogue order. 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
- Math-111 NP-Completeness of the Minimum Circuit Size Problem (MCSP)
- Math-155 Polynomial pivot rule for the simplex method
- Math-203 Metric TSP Subtour LP Integrality Gap Conjecture
- Math-273 Polynomial-Time Decidability of Semidefinite Programming Feasibility
- Math-428 Polynomial-Time P-Matrix Linear Complementarity Problem
- Math-441 Deterministic Linear-Time Minimum Spanning Tree Problem
- Math-513 Smale's 9th Problem: Linear Programming in Polynomial Time
- Math-2073 10 Lectures and 42 Open Problems — Sum of Squares approximation ratio for Max-Cut
- Math-2420 Polynomial Algorithms for Mean-Payoff Games and Linear Programming
- Math-2963 Bounded additive gap for the bin-packing configuration LP
- Math-2981 Exponential semidefinite complexity for perfect matching
- Math-2982 Optimal Max-Cut approximation hardness
- Math-2984 Metric k-median at factor one plus two over e
- Math-2985 Metric k-median strictly below factor two
- Math-2999 Almost-linear maximum-cardinality matching
- Math-3007 Polynomial-time three-machine unit-job scheduling
- Math-3036 The Polynomial Hirsch Conjecture
- Math-3790 10 Lectures and 42 Open Problems — Tightness of the Multireference Alignment SDP
- Math-4376 10 Lectures and 42 Open Problems — Maximum and minimum bisections on random regular graphs
- Math-4377 10 Lectures and 42 Open Problems — Sharp tightness of the Angular Synchronization SDP
- Math-4401 ML degree, feasibility, and a Gaussian likelihood-root trichotomy
- Math-4465 Central-Trajectory Integral Bounds
- Math-4472 Integral Primal Certificates for Submodular Minimization
- Math-4474 Sampling Algorithms for Maximum-Cut Density
- Math-4487 Convex-Hull Decomposition for Mixed-Integer Bipartite Systems
- Math-4489 Linear Optimization over Mixed-Integer Bipartite Systems
- Math-4492 Optimal Feasible Sets from Quantized Trajectory Observations
- Math-4508 Efficient Moment Relaxations for Polynomial Optimization
- Math-4511 Polynomial-Time Minimization of K-Submodular Functions
- Math-4512 Complexity of Maximizing Initial Odd Ears
- Math-4513 Additive Integrality Gap for Ring Loading
- Math-4514 Exact Integrality Gap for Capacitated Facility Location
- Math-4515 Compact Constant-Gap Relaxations for Capacitated Facility Location
- Math-4535 Practical Sum-of-Squares Tensor Completion
- Math-4537 Global Optimization of Overparameterized Shallow Networks
- Math-4538 Extrapolating Clusterings from Semidefinite Subsamples
- Math-4539 Local Approximation of Random-Graph Semidefinite Programs
- Math-4541 Proximity and Sparsity of Optimal Integer Solutions
- Math-4542 Convergence Rates for Convex-Body Bounds
- Math-4543 Fast Low-Rank Maximum-Weight Assignment
- Math-4544 Integrality Gaps for Directed Linear k-Cut
- Math-4545 Hardness of Root-Dependent Spanning-Tree Optimization
- Math-4546 Hardness of Path-Cost Arborescence Optimization
- Math-4548 Degree-Utility Optimization in Graphs
- Math-4552 Geometric Explanations and Polynomial Pivot Rules for Simplex
- Math-4553 Sharp Smoothed Complexity of Simplex Pivot Rules
- Math-4560 Semidefinite Hierarchies for Equiangular Line Bounds
- Math-4563 Minimum Crossing Realizations of Spatial Polygon Angle Sequences
- Math-4566 Integer Programming with Bounded Subdeterminants
- Math-4568 Arborescences Induced by Linear-Programming Pivot Rules