Breaking symmetries to rescue sum of squares in the case of makespan scheduling (Q2196315): Difference between revisions

Revision as of 09:21, 23 July 2024

scientific article; zbMATH DE number 7164376

Breaking symmetries to rescue sum of squares: the case of makespan scheduling

Language	Label	Description	Also known as
English	Breaking symmetries to rescue sum of squares in the case of makespan scheduling	scientific article; zbMATH DE number 7164376	Breaking symmetries to rescue sum of squares: the case of makespan scheduling

Statements

instance of

scholarly article

0 references

title

Breaking symmetries to rescue sum of squares in the case of makespan scheduling (English)

0 references

Breaking symmetries to rescue sum of squares: the case of makespan scheduling (English)

0 references

0 references

0 references

0 references

Mathematical Programming. Series A. Series B

0 references

publication date

28 August 2020

0 references

6 February 2020

0 references

full work available at URL

https://arxiv.org/abs/1811.08539

0 references

zbMATH Keywords

makespan scheduling

0 references

polynomial optimization

0 references

approximation algorithms

0 references

symmetry breaking

0 references

0 references

0 references

Approximation schemes for scheduling on parallel machines

0 references

Q4052481

0 references

Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators

0 references

Sum of Squares Lower Bounds from Pairwise Independence

0 references

A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem

0 references

Sums of squares on the hypercube

0 references

Convex Relaxations and Integrality Gaps

0 references

Q3413659

0 references

Q4607934

0 references

Quasi-PTAS for scheduling with precedences using LP hierarchies

0 references

Symmetry groups, semidefinite programs, and sums of squares

0 references

Polynomiality for Bin Packing with a Constant Number of Item Types

0 references

Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

0 references

Bounds for Certain Multiprocessing Anomalies

0 references

Complexity of Positivstellensatz proofs for the knapsack

0 references

Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity

0 references

Q3002852

0 references

An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables

0 references

Q4598212

0 references

Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack

0 references

Sum of squares lower bounds for refuting any CSP

0 references

Robust moment estimation and improved clustering via sum of squares

0 references

On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy

0 references

Sum-of-squares hierarchy lower bounds for symmetric formulations

0 references

An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem

0 references

Semidefinite and linear programming integrality gaps for scheduling identical machines

0 references

Global Optimization with Polynomials and the Problem of Moments

0 references

A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming

0 references

Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope

0 references

Semidefinite representations for finite varieties

0 references

Q3601990

0 references

A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies

0 references

Symmetry in Integer Linear Programming

0 references

High degree sum of squares proofs, Bienstock-Zuckerberg hierarchy and CG cuts

0 references

Semidefinite programming relaxations for semialgebraic problems

0 references

Symmetric sums of squares over \(k\)-subset hypercubes

0 references

Flag algebras

0 references

On 3-Hypergraphs with Forbidden 4-Vertex Configurations

0 references

Q2716065

0 references

A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems

0 references

Santa Claus Schedules Jobs on Unrelated Machines

0 references

Breaking symmetries to rescue sum of squares in the case of makespan scheduling

0 references

The Design of Approximation Algorithms

0 references

Identifiers

zbMATH Open document ID

1453.90079

0 references

1436.90080

0 references

DOI

10.1007/s10107-020-01511-3

0 references

10.1007/978-3-030-17953-3_32

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:2196315

@@ Property / cites work @@
+Q5501827
@@ Property / cites work: Q5501827 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation schemes for scheduling on parallel machines
+Normal rank
@@ Property / cites work @@
+Q4052481
@@ Property / cites work: Q4052481 / rank @@
+Normal rank
@@ Property / cites work @@
+Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators
+Normal rank
@@ Property / cites work @@
+Sum of Squares Lower Bounds from Pairwise Independence
+Normal rank
@@ Property / cites work @@
+A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
+Normal rank
@@ Property / cites work @@
+Sums of squares on the hypercube
@@ Property / cites work: Sums of squares on the hypercube / rank @@
+Normal rank
@@ Property / cites work @@
+Convex Relaxations and Integrality Gaps
@@ Property / cites work: Convex Relaxations and Integrality Gaps / rank @@
+Normal rank
@@ Property / cites work @@
+Q3413659
@@ Property / cites work: Q3413659 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4607934
@@ Property / cites work: Q4607934 / rank @@
+Normal rank
@@ Property / cites work @@
+Quasi-PTAS for scheduling with precedences using LP hierarchies
+Normal rank
@@ Property / cites work @@
+Symmetry groups, semidefinite programs, and sums of squares
+Normal rank
@@ Property / cites work @@
+Polynomiality for Bin Packing with a Constant Number of Item Types
+Normal rank
@@ Property / cites work @@
+Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
+Normal rank
@@ Property / cites work @@
+Bounds for Certain Multiprocessing Anomalies
@@ Property / cites work: Bounds for Certain Multiprocessing Anomalies / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity of Positivstellensatz proofs for the knapsack
+Normal rank
@@ Property / cites work @@
+Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
+Normal rank
@@ Property / cites work @@
+Q3002852
@@ Property / cites work: Q3002852 / rank @@
+Normal rank
@@ Property / cites work @@
+An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables
+Normal rank
@@ Property / cites work @@
+Q4598212
@@ Property / cites work: Q4598212 / rank @@
+Normal rank
@@ Property / cites work @@
+Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack
+Normal rank
@@ Property / cites work @@
+Sum of squares lower bounds for refuting any CSP
@@ Property / cites work: Sum of squares lower bounds for refuting any CSP / rank @@
+Normal rank
@@ Property / cites work @@
+Robust moment estimation and improved clustering via sum of squares
+Normal rank
@@ Property / cites work @@
+On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy
+Normal rank
@@ Property / cites work @@
+Sum-of-squares hierarchy lower bounds for symmetric formulations
+Normal rank
@@ Property / cites work @@
+An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem
+Normal rank
@@ Property / cites work @@
+Semidefinite and linear programming integrality gaps for scheduling identical machines
+Normal rank
@@ Property / cites work @@
+Global Optimization with Polynomials and the Problem of Moments
+Normal rank
@@ Property / cites work @@
+A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
+Normal rank
@@ Property / cites work @@
+Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
+Normal rank
@@ Property / cites work @@
+Semidefinite representations for finite varieties
@@ Property / cites work: Semidefinite representations for finite varieties / rank @@
+Normal rank
@@ Property / cites work @@
+Q3601990
@@ Property / cites work: Q3601990 / rank @@
+Normal rank
@@ Property / cites work @@
+A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies
+Normal rank
@@ Property / cites work @@
+Symmetry in Integer Linear Programming
@@ Property / cites work: Symmetry in Integer Linear Programming / rank @@
+Normal rank
@@ Property / cites work @@
+High degree sum of squares proofs, Bienstock-Zuckerberg hierarchy and CG cuts
+Normal rank
@@ Property / cites work @@
+Semidefinite programming relaxations for semialgebraic problems
+Normal rank
@@ Property / cites work @@
+Symmetric sums of squares over \(k\)-subset hypercubes
+Normal rank
@@ Property / cites work @@
+Flag algebras
@@ Property / cites work: Flag algebras / rank @@
+Normal rank
@@ Property / cites work @@
+On 3-Hypergraphs with Forbidden 4-Vertex Configurations
+Normal rank
@@ Property / cites work @@
+Q2716065
@@ Property / cites work: Q2716065 / rank @@
+Normal rank
@@ Property / cites work @@
+A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
+Normal rank
@@ Property / cites work @@
+Santa Claus Schedules Jobs on Unrelated Machines
@@ Property / cites work: Santa Claus Schedules Jobs on Unrelated Machines / rank @@
+Normal rank
@@ Property / cites work @@
+Breaking symmetries to rescue sum of squares in the case of makespan scheduling
+Normal rank
@@ Property / cites work @@
+The Design of Approximation Algorithms
@@ Property / cites work: The Design of Approximation Algorithms / rank @@
+Normal rank