Superlinear Integrality Gaps for the Minimum Majority Problem
From MaRDI portal
Recommendations
- Integrality gaps for Sherali-Adams relaxations
- Proving integrality gaps without knowing the linear program
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- CSP gaps and reductions in the lasserre hierarchy
Cites work
- A $(\log n)^{\Omega(1)}$ Integrality Gap for the Sparsest Cut SDP
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- A decision-theoretic generalization of on-line learning and an application to boosting
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- A note on the hardness of sparse approximation
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Boosting the margin: a new explanation for the effectiveness of voting methods
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Convergence of stochastic processes
- Convex relaxations and integrality gaps
- Distribution inequalities for the binomial law
- Every linear threshold function has a low-weight approximator
- Extending SDP integrality gaps to Sherali-Adams with applications to quadratic programming and MaxCutGain
- scientific article; zbMATH DE number 5485464 (Why is no real title available?)
- scientific article; zbMATH DE number 741240 (Why is no real title available?)
- scientific article; zbMATH DE number 1830719 (Why is no real title available?)
- scientific article; zbMATH DE number 819814 (Why is no real title available?)
- Improved boosting algorithms using confidence-rated predictions
- Integrality gaps for colorful matchings
- Integrality gaps for Sherali-Adams relaxations
- Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES
- Integrality gaps of 2-o(1) for vertex cover SDPs in the Lovász-Schrijver hierarchy
- Integrality gaps of linear and semi-definite programming relaxations for knapsack
- Linear programming relaxations of \textsc{maxcut}
- No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)
- On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
- On the ratio of optimal integral and fractional covers
- Optimal Sherali-Adams Gaps from Pairwise Independence
- Polynomial integrality gaps for strong SDP relaxations of densest k-subgraph
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Proving integrality gaps without knowing the linear program
- Rank bounds and integrality gaps for cutting planes procedures
- SDP Integrality Gaps with Local ell₁-Embeddability
- Semialgebraic Proofs and Efficient Algorithm Design
- Semidefinite and linear programming integrality gaps for scheduling identical machines
- Sherali-Adams integrality gaps matching the log-density threshold
- Sherali-Adams relaxations of the matching polytope
- The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into _1
- Threshold circuits of bounded depth
- Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy
- Towards strong nonapproximability results in the Lovász-Schrijver hierarchy
- When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?
This page was built for publication: Superlinear Integrality Gaps for the Minimum Majority Problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5020845)
