On the extension complexity of scheduling polytopes

DOI10.1016/j.orl.2020.05.008zbMath1478.90044OpenAlexW3027425305MaRDI QIDQ2661503

Hans Raj Tiwary, Andreas Wiese, Víctor Verdugo

Publication date: 7 April 2021

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2020.05.008

zbMATH Keywords

linear programmingextended formulationsmakespan scheduling

Mathematics Subject Classification ID

Linear programming (90C05) Deterministic scheduling theory in operations research (90B35)

Related Items (1)

Sparktope: linear programs from algorithms

Cites Work

• Unnamed Item
• On the extension complexity of combinatorial polytopes
• Approximation algorithms for scheduling unrelated parallel machines
• Using separation algorithms to generate mixed integer model reformulations
• Expressing combinatorial optimization problems by linear programs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A quasi-polynomial approximation for the restricted assignment problem
• Some \(0/1\) polytopes need exponential size extended formulations
• Graph balancing: a special case of scheduling unrelated parallel machines
• An optimal rounding gives a better approximation for scheduling unrelated machines
• Exponential Lower Bounds for Polytopes in Combinatorial Optimization
• Better Bin Packing Approximations via Discrepancy Theory
• Polyhedral Characterization of Discrete Dynamic Programming
• Reformulation and Decomposition of Integer Programs
• A Logarithmic Additive Integrality Gap for Bin Packing
• Extension Complexity of Independent Set Polytopes
• The Matching Polytope has Exponential Extension Complexity
• Santa Claus Schedules Jobs on Unrelated Machines
• Matroids and the greedy algorithm
• Extended formulations in combinatorial optimization

This page was built for publication: On the extension complexity of scheduling polytopes