scientific article; zbMATH DE number 7009613

DOI10.4086/toc.2018.v014a014zbMath1426.90211OpenAlexW2904298817MaRDI QIDQ4612478

Sangxia Huang, Ola Svensson, Samuel Fiorini, Abbas Bazzi

Publication date: 31 January 2019

Published in: Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4086/toc.2018.v014a014

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

linear programmingknapsackcommunication complexityextended formulations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (2)

A Water-Filling Primal-Dual Algorithm for Approximating NonLinear Covering Problems ⋮ Approximation algorithms for cost-robust discrete minimization problems based on their LP-relaxations

Cites Work

• Unnamed Item
• Unnamed Item
• Tightening simple mixed-integer sets with guaranteed bounds
• On the nonnegative rank of distance matrices
• Extended formulations, nonnegative factorizations, and randomized communication protocols
• Primal-dual schema for capacitated covering problems
• Approximate formulations for 0-1 knapsack sets
• Monotone circuits for monotone weighted threshold functions
• Sorting in \(c \log n\) parallel steps
• Expressing combinatorial optimization problems by linear programs
• A note on the extension complexity of the knapsack polytope
• Theory of majority decision elements
• Exponential Lower Bounds for Polytopes in Combinatorial Optimization
• Randomized Competitive Algorithms for Generalized Caching
• Lower Bounds on the Size of Semidefinite Programming Relaxations
• LP-Based Algorithms for Capacitated Facility Location
• Approximation Algorithms for the Capacitated Multi-Item Lot-Sizing Problem via Flow-Cover Inequalities
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• Approximate Deadline-Scheduling with Precedence Constraints
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Valid Linear Inequalities for Fixed Charge Problems
• Fast Approximation Algorithms for Knapsack Problems
• Faces for a linear inequality in 0–1 variables
• Facet of regular 0–1 polytopes
• Facets of the knapsack polytope
• Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits
• Extension Complexity of Independent Set Polytopes
• Addition is exponentially harder than counting for shallow monotone circuits
• Reducibility among Combinatorial Problems
• The Geometry of Scheduling
• Extended formulations in combinatorial optimization

This page was built for publication: