Superlinear Integrality Gaps for the Minimum Majority Problem

DOI10.1137/20M1359584OpenAlexW4206420102MaRDI QIDQ5020845

Philip M. Long

Publication date: 7 January 2022

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/20m1359584

zbMATH Keywords

approximation algorithmsrandomized roundinginapproximabilityintegrality gapslift-and-projectsparse machine learning

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Linear programming (90C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Fixed-time stabilization of generalized leakage-delayed neural networks with discontinuous disturbances via mixed-delay-product-type LKF

Uses Software

• AdaBoost.MH

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Towards strong nonapproximability results in the Lovász-Schrijver hierarchy
• Primal-dual approximation algorithms for integral flow and multicut in trees
• On the ratio of optimal integral and fractional covers
• Distribution inequalities for the binomial law
• On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
• A decision-theoretic generalization of on-line learning and an application to boosting
• Semidefinite and linear programming integrality gaps for scheduling identical machines
• Boosting the margin: a new explanation for the effectiveness of voting methods
• Improved boosting algorithms using confidence-rated predictions
• Threshold circuits of bounded depth
• Integrality gaps for colorful matchings
• A note on the hardness of sparse approximation
• Every linear threshold function has a low-weight approximator
• Convex Relaxations and Integrality Gaps
• Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Extending SDP Integrality Gaps to Sherali-Adams with Applications to Quadratic Programming and MaxCutGain
• Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy
• Optimal Sherali-Adams Gaps from Pairwise Independence
• Cones of Matrices and Set-Functions and 0–1 Optimization
• A $(\log n)^{\Omega(1)}$ Integrality Gap for the Sparsest Cut SDP
• SDP Integrality Gaps with Local ell_1-Embeddability
• Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES
• Integrality gaps for Sherali-Adams relaxations
• Sherali-adams relaxations of the matching polytope
• Semialgebraic Proofs and Efficient Algorithm Design
• No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ
• Integrality Gaps of $2-o(1)$ for Vertex Cover SDPs in the Lovász–Schrijver Hierarchy
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ ₁
• When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• Convergence of stochastic processes

This page was built for publication: Superlinear Integrality Gaps for the Minimum Majority Problem