Breaking symmetries to rescue sum of squares in the case of makespan scheduling
From MaRDI portal
Publication:2196315
DOI10.1007/s10107-020-01511-3zbMath1453.90079arXiv1811.08539OpenAlexW2900646172MaRDI QIDQ2196315
José Verschae, Andreas Wiese, Víctor Verdugo
Publication date: 28 August 2020
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1811.08539
Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Boolean programming (90C09) Approximation algorithms (68W25) Polynomial optimization (90C23)
Related Items
A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time, Breaking symmetries to rescue sum of squares in the case of makespan scheduling
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sums of squares on the hypercube
- Semidefinite representations for finite varieties
- Approximation schemes for scheduling on parallel machines
- Semidefinite programming relaxations for semialgebraic problems
- Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators
- An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem
- Symmetric sums of squares over \(k\)-subset hypercubes
- Semidefinite and linear programming integrality gaps for scheduling identical machines
- Symmetry groups, semidefinite programs, and sums of squares
- Sum-of-squares hierarchy lower bounds for symmetric formulations
- Breaking symmetries to rescue sum of squares in the case of makespan scheduling
- High degree sum of squares proofs, Bienstock-Zuckerberg hierarchy and CG cuts
- Global Optimization with Polynomials and the Problem of Moments
- Convex Relaxations and Integrality Gaps
- Sum of Squares Lower Bounds from Pairwise Independence
- On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy
- On 3-Hypergraphs with Forbidden 4-Vertex Configurations
- Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack
- The Design of Approximation Algorithms
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Symmetry in Integer Linear Programming
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
- Santa Claus Schedules Jobs on Unrelated Machines
- Sum of squares lower bounds for refuting any CSP
- Quasi-PTAS for scheduling with precedences using LP hierarchies
- Robust moment estimation and improved clustering via sum of squares
- A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies
- Polynomiality for Bin Packing with a Constant Number of Item Types
- An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables
- Flag algebras
- Bounds for Certain Multiprocessing Anomalies
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
- Complexity of Positivstellensatz proofs for the knapsack
