Thomas Rothvoß

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

The Extension Complexity of Polytopes with Bounded Integral Slack Matrices.

[BibT_eX]

[DOI]

Sally Dong

Proceedings of the Integer Programming and Combinatorial Optimization, 2024

2023

Vector balancing in Lebesgue spaces.

[BibT_eX]

[DOI]

Random Struct. Algorithms, May, 2023

Stronger Coreset Bounds for Kernel Density Estimators via Chaining.

[BibT_eX]

[DOI]

Rainie Bozzai

CoRR, 2023

Polytopes with Bounded Integral Slack Matrices Have Sub-Exponential Extension Complexity.

[BibT_eX]

[DOI]

Sally Dong

CoRR, 2023

From Approximate to Exact Integer Programming.

[BibT_eX]

[DOI]

Daniel Dadush

Proceedings of the Integer Programming and Combinatorial Optimization, 2023

The Subspace Flatness Conjecture and Faster Integer Programming.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

The Vector Balancing Constant for Zonotopes.

[BibT_eX]

[DOI]

Rainie Bozzai

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

The Vector Balancing Constant for Zonotopes.

[BibT_eX]

[DOI]

Laurel Heck

CoRR, 2022

Approximate Carathéodory bounds via Discrepancy Theory.

[BibT_eX]

[DOI]

CoRR, 2022

On the Hardness of Scheduling With Non-Uniform Communication Delays.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Approximate $\mathrm {CVP}_{}$ in Time 2<sup>0.802 n</sup> - Now in Any Norm!

[BibT_eX]

[DOI]

Moritz Venzin

Proceedings of the Integer Programming and Combinatorial Optimization, 2022

2021

A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies.

[BibT_eX]

[DOI]

Elaine Levey

SIAM J. Comput., 2021

Tight bounds on the Fourier growth of bounded functions on the hypercube.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Approximate CVP in time 2<sup>0.802 n</sup> - now in any norm!

[BibT_eX]

[DOI]

Moritz Venzin

CoRR, 2021

Improved Analysis of Online Balanced Clustering.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms - 19th International Workshop, 2021

Scheduling with Communication Delays via LP Hierarchies and Clustering II: Weighted Completion Times on Related Machines.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

2020

Polynomiality for Bin Packing with a Constant Number of Item Types.

[BibT_eX]

[DOI]

Michel X. Goemans

J. ACM, 2020

Linear Size Sparsifier and the Geometry of the Operator Norm Ball.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

A Tale of Santa Claus, Hypergraphs and Matroids.

[BibT_eX]

[DOI]

Sami Davies

Yihao Zhang

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Scheduling with Communication Delays via LP Hierarchies and Clustering.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

A Fourier-Analytic Approach for the Discrepancy of Random Set Systems.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2017

Constructive Discrepancy Minimization for Convex Sets.

[BibT_eX]

[DOI]

SIAM J. Comput., 2017

The Matching Polytope has Exponential Extension Complexity.

[BibT_eX]

[DOI]

J. ACM, 2017

0/1 Polytopes with Quadratic Chvátal Rank.

[BibT_eX]

[DOI]

Laura Sanità

Oper. Res., 2017

A Logarithmic Additive Integrality Gap for Bin Packing.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Deterministic Discrepancy Minimization via the Multiplicative Weight Update Method.

[BibT_eX]

[DOI]

Avi Levy

Harishchandra Ramadas

Proceedings of the Integer Programming and Combinatorial Optimization, 2017

Number Balancing is as Hard as Minkowski's Theorem and Shortest Vector.

[BibT_eX]

[DOI]

Harishchandra Ramadas

Xin Yang

Proceedings of the Integer Programming and Combinatorial Optimization, 2017

An Improved Deterministic Rescaling for Linear Programming Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2017

2016

Better Bin Packing Approximations via Discrepancy Theory.

[BibT_eX]

[DOI]

SIAM J. Comput., 2016

Pricing on Paths: A PTAS for the Highway Problem.

[BibT_eX]

[DOI]

SIAM J. Comput., 2016

Lecture Notes on the ARV Algorithm for Sparsest Cut.

[BibT_eX]

[DOI]

CoRR, 2016

2015

Exact comparison of fixed priority and EDF scheduling based on speedup factors for both pre-emptive and non-pre-emptive paradigms.

[BibT_eX]

[DOI]

Real Time Syst., 2015

A Lasserre-based $(1+\varepsilon)$-approximation for $Pm \mid p_j=1, \textrm{prec} \mid C_{\max}$.

[BibT_eX]

[DOI]

Elaine Levey

CoRR, 2015

2014

A direct proof for Lovett's bound on the communication complexity of low rank matrices.

[BibT_eX]

[DOI]

CoRR, 2014

2013

Bin Packing via Discrepancy of Permutations.

[BibT_eX]

[DOI]

Dömötör Pálvölgyi

ACM Trans. Algorithms, 2013

Cover-Decomposition and Polychromatic Numbers.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2013

Some 0/1 polytopes need exponential size extended formulations.

[BibT_eX]

[DOI]

Math. Program., 2013

Steiner Tree Approximation via Iterative Randomized Rounding.

[BibT_eX]

[DOI]

J. ACM, 2013

A Simpler Proof for $O(\textrm{Congestion} + \textrm{Dilation})$ Packet Routing.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2013

Approximating Bin Packing within O(log OPT * Log Log OPT) Bins.

[BibT_eX]

[DOI]

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012

Extended Formulations for Polygons.

[BibT_eX]

[DOI]

Samuel Fiorini

Hans Raj Tiwary

Discret. Comput. Geom., 2012

A simpler proof for O(congestion + dilation) packet routing

[BibT_eX]

[DOI]

CoRR, 2012

Matroids and integrality gaps for hypergraphic steiner tree relaxations.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

The entropy rounding method in approximation algorithms.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

2011

From Uncertainty to Nonlinearity: Solving Virtual Private Network via Single-Sink Buy-at-Bulk.

[BibT_eX]

[DOI]

Laura Sanità

Math. Oper. Res., 2011

Directed Steiner Tree and the Lasserre Hierarchy

[BibT_eX]

[DOI]

CoRR, 2011

Approximation Algorithms for Single and Multi-Commodity Connected Facility Location.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatoral Optimization, 2011

Set Covering with Ordered Replacement: Additive and Multiplicative Gaps.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatoral Optimization, 2011

2010

Diameter of Polyhedra: Limits of Abstraction.

[BibT_eX]

[DOI]

Nicolai Hähnle

Alexander A. Razborov

Math. Oper. Res., 2010

Connected facility location via random facility sampling and core detouring.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2010

Optimal Selection of Customers for a Last-Minute Offer.

[BibT_eX]

[DOI]

Oper. Res., 2010

Edge-Colouring Hypergraphs Properly (Covering with Matchings) or Polychromatically (Packing Covers)

[BibT_eX]

[DOI]

David Pritchard

CoRR, 2010

Prizing on Paths: A PTAS for the Highway Problem

[BibT_eX]

[DOI]

CoRR, 2010

A 3/2-Approximation Algorithm for Rate-Monotonic Multiprocessor Scheduling of Implicit-Deadline Tasks.

[BibT_eX]

[DOI]

Andreas Karrenbauer

Proceedings of the Approximation and Online Algorithms - 8th International Workshop, 2010

An improved LP-based approximation for steiner tree.

[BibT_eX]

[DOI]

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

EDF-schedulability of Synchronous Periodic Task Systems is coNP-hard.

[BibT_eX]

[DOI]

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Network Design via Core Detouring for Problems without a Core.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Recent Hardness Results for Periodic Uni-processor Scheduling.

[BibT_eX]

[DOI]

Proceedings of the Scheduling, 14.02. - 19.02.2010, 2010

2009

Exact quantification of the sub-optimality of uniprocessor fixed priority pre-emptive scheduling.

[BibT_eX]

[DOI]

Real Time Syst., 2009

An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-Time Scheduling.

[BibT_eX]

[DOI]

Andreas Karrenbauer

Proceedings of the Algorithms, 2009

Diameter of polyhedra: limits of abstraction.

[BibT_eX]

[DOI]

Nicolai Hähnle

Proceedings of the 25th ACM Symposium on Computational Geometry, 2009

On the Complexity of the Asymmetric VPN Problem.

[BibT_eX]

[DOI]

Laura Sanità

Proceedings of the Approximation, 2009

New Hardness Results for Diophantine Approximation.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2009

2008

Convexly Independent Subsets of the Minkowski Sum of Planar Point Sets.

[BibT_eX]

[DOI]

Electron. J. Comb., 2008

Approximating connected facility location problems via random facility sampling and core detouring.

[BibT_eX]

[DOI]

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Static-Priority Real-Time Scheduling: Response Time Computation Is NP-Hard.

[BibT_eX]

[DOI]

Proceedings of the 29th IEEE Real-Time Systems Symposium, 2008

A PTAS for Static Priority Real-Time Scheduling with Resource Augmentation.

[BibT_eX]

[DOI]