For a real matrix \(\textbf A \in \mathbb{R}^{d \times n}\) with non-collinear columns, we show that \(n \le O(d^{4} \kappa_\textbf A)\) where \(\kappa_\textbf A\) is the circuit imbalance measure of \(\textbf A\). The circuit imbalance measure \(\kappa\) is a real analogue of \(\Delta\)-modularity for integer matrices, satisfying \(\kappa_\textbf A \le \Delta_\textbf A\) for integer \(\textbf A\). The circuit imbalance measure has numerous applications in the context of linear programming (see Ekkbatani, Natura and Végh (2022) for a survey). Our result generalizes the \(O(d^{4} \Delta_\textbf A)\) bound of Averkov and Schymura (2023) for integer matrices and provides the first polynomial bound holding for all parameter ranges on real matrices.

Let \(A \in \mathbb{Z}^{m \times n}\) be an integer matrix with entries bounded by \(\Delta\) in absolute value. Cook et al. (1986) have shown that there exists a universal matrix \(B \in \mathbb{Z}^{m' \times n}\) with the following property: For each \(b \in \mathbb{Z}^m\), there exists a \(t \in \mathbb{Z}^{m'}\) such that the integer hull of the polyhedron \(P = \{x \in \mathbb{R}^n : Ax \le b\}\) is described by \(P_I = \{x \in \mathbb{R}^n : Bx \le t\}\). Our main result is that \(t\) is an affine function of \(b\) as long as \(b\) is from a fixed equivalence class of the lattice \(D \cdot \mathbb{Z}^m\). Here \(D \in \mathbb{N}\) is a number that depends on \(n\) and \(\Delta\) only. Furthermore, \(D\) as well as the matrix \(B\) can be computed in time depending on \(n\) and \(\Delta\) only. An application of this result is the solution of an open problem posed by Cslovjecsek et al. (SODA 2024) concerning the complexity of 2-stage-stochastic integer programming problems. The main tool of our proof is the classical theory of Chvátal-Gomory cutting planes and the elementary closure of rational polyhedra.

Quantizing the weights of a neural network has two steps: (1) Finding a good low bit-complexity representation for weights (which we call the quantization grid) and (2) Rounding the original weights to values in the quantization grid. In this paper, we study the problem of rounding optimally given any quantization grid. The simplest and most commonly used way to round is Round-to-Nearest (RTN). By rounding in a data-dependent way instead, one can improve the quality of the quantized model significantly. We study the rounding problem from the lens of \emph{discrepancy theory}, which studies how well we can round a continuous solution to a discrete solution without affecting solution quality too much. We prove that given $m=\poly\left(\frac{\log n}{\epsilon}\right)$ samples from the data distribution, we can round nearly all $n$ model parameters such that the expected approximation error of the quantized model on the true data distribution is $\le \epsilon$ as long as the space of gradients of the original model is approximately low rank (which we empirically validate). Our algorithm is based on the famous Lovett-Meka algorithm from discrepancy theory and uses sticky Brownian motion to find a good rounding. We also give a simple and practical rounding algorithm called \emph{DiscQuant}, which is inspired by our theoretical insights. In our experiments, we demonstrate that DiscQuant significantly improves over the prior state-of-the-art rounding method called GPTQ and the baseline RTN over a range of benchmarks on Phi3mini-3.8B and Llama3.1-8B. For example, rounding Phi3mini-3.8B to a fixed quantization grid with 3.25 bits per parameter using DiscQuant gets 64% accuracy on the GSM8k dataset, whereas GPTQ achieves 54% and RTN achieves 31% (the original model achieves 84%). We make our code available at \url{https://github.com/jerry-chee/DiscQuant}.

Given a convex set Q ⊆ ℝm and an integer matrix W ∈ ℤm×n, we consider statements of the form ∀b ∈ Q ∩ ℤm ∃x ∈ ℤn s.t. Wx ≤ b. Such statements can be verified in polynomial time with the algorithm of Kannan and its improvements if n is fixed and Q is a polyhedron. The running time of the best-known algorithms is doubly exponential in n. We provide a pseudopolynomial-time algorithm if m is fixed. Its running time is (mΔ)O (m2 ) where Δ is the largest absolute value of an entry in W. Furthermore it applies to general convex sets Q.

We prove that there exists an online algorithm that for any sequence of vectors v1,…,vT ∈ ℝn with ||vi||2 ≤ 1, arriving one at a time, decides random signs x1,…,xT ∈ { −1,1} so that for every t ≤ T, the prefix sum ∑i=1t xivi is 10-subgaussian. This improves over the work of Alweiss, Liu and Sawhney who kept prefix sums O(√log(nT))-subgaussian, and gives a O(√logT) bound on the discrepancy maxt ∈ T ||∑i=1t xi vi||∞. Our proof combines a generalization of Banaszczyk’s prefix balancing result to trees with a cloning argument to find distributions rather than single colorings. We also show a matching Ω(√logT) strategy for an oblivious adversary.

The vector balancing constant $\operatorname{vb}(K, Q)$ of two symmetric convex bodies $K, Q$ is the minimum $r \geq 0$ so that any number of vectors from K can be balanced into an r scaling of Q. A question raised by Schechtman is whether for any zonotope $K \subseteq \mathbb{R}^{d}$ one has $\operatorname{vb}(K, K) \lesssim \sqrt{d}$. Intuitively, this asks whether a natural geometric generalization of Spencer’s Theorem (for which $K=B_{\infty}^{d}$) holds. We prove that for any zonotope $K \subseteq \mathbb{R}^{d}$ one has $\operatorname{vb}(K, K) \lesssim \sqrt{d} \log \log \log d$. Our main technical contribution is a tight lower bound on the Gaussian measure of any section of a normalized zonotope, generalizing Vaaler’s Theorem for cubes. We also prove that for two different normalized zonotopes K and Q one has $\operatorname{vb}(K, Q) \lesssim \sqrt{d \log d}$. All the bounds are constructive and the corresponding colorings can be computed in polynomial time.

In a seminal paper, Kannan and Lovász (1988) considered a quantity $\mu_{K L}(\Lambda, K)$ which denotes the best volume-based lower bound on the covering radius $\mu(\Lambda, K)$ of a convex body K with respect to a lattice $\Lambda$. Kannan and Lovász proved that $\mu(\Lambda, K) \leq n \cdot \mu_{K L}(\Lambda, K)$ and the Subspace Flatness Conjecture by Dadush (2012) claims a $O(\log (2 n))$ factor suffices, which would match the lower bound from the work of Kannan and Lovász. We settle this conjecture up to a constant in the exponent by proving that $\mu(\Lambda, K) \leq$ $O\left(\log ^{3}(2 n)\right) \cdot \mu_{K L}(\Lambda, K)$. Our proof is based on the Reverse Minkowski Theorem due to Regev and Stephens-Davidowitz (2017). Following the work of Dadush $(2012,2019)$, we obtain a $(\log (2 n))^{O(n)}$-time randomized algorithm to solve integer programs in n variables. Another implication of our main result is a near-optimal flatness constant of $O\left(n \log ^{3}(2 n)\right)$.

In the problem of scheduling with non-uniform communication delays, the input is a set of jobs with precedence constraints. Associated with every precedence constraint between a pair of jobs is a communication delay, the time duration the scheduler has to wait between the two jobs if they are scheduled on different machines. The objective is to assign the jobs to machines to minimize the makespan of the schedule. Despite being a fundamental problem in theory and a consequential problem in practice, the approximability of scheduling problems with communication delays is not very well understood. One of the top ten open problems in scheduling theory, in the influential list by Schuurman and Woeginger and its latest update by Bansal, asks if the problem admits a constant-factor approximation algorithm. In this paper, we answer this question in the negative by proving a logarithmic hardness for the problem under the standard complexity theory assumption that NP-complete problems do not admit quasi-polynomial-time algorithms. Our hardness result is obtained using a surprisingly simple reduction from a problem that we call Unique Machine Precedence constraints Scheduling (UMPS). We believe that this problem is of central importance in understanding the hardness of many scheduling problems and we conjecture that it is very hard to approximate. Among other things, our conjecture implies a logarithmic hardness of related machine scheduling with precedences, a long-standing open problem in scheduling theory and approximation algorithms.

We consider the problem of scheduling jobs with precedence constraints on related machines to minimize the weighted sum of completion times, in the presence of communication delays. In this setting, denoted by Q | prec, c | ΣwjCj, if two dependent jobs are scheduled on different machines, then at least c units of communication delay time must pass between their executions. Our main result is an O(log4 n)-approximation algorithm for the problem. As a byproduct of our result, we also obtain an O(log3 n)-approximation algorithm for the problem of minimizing makespan Q | prec, c | Cmax, which improves upon the O(log5 n/ log log n)-approximation algorithm due to a recent work of Maiti et al. [MRS+20].

In a classical problem in scheduling, one has $n$ unit size jobs with a precedence order and the goal is to find a schedule of those jobs on $m$ identical machines as to minimize the makespan. It is one of the remaining four open problems from the book of Garey and Johnson whether or not this problem is $\mathbf{NP}$-hard for $m=3$. We prove that for any fixed $\varepsilon$ and $m$, an LP-hierarchy lift of the time-indexed LP with a slightly super poly-logarithmic number of $r = (\log(n))^{\Theta(\log \log n)}$ rounds provides a $(1 + \varepsilon)$-approximation. For example, Sherali--Adams suffices as hierarchy. This implies an algorithm that yields a $(1+\varepsilon)$-approximation in time $n^{O(r)}$. The previously best approximation algorithms guarantee a $2 - \frac{7}{3m+1}$-approximation in polynomial time for $m \geq 4$ and $\frac{4}{3}$ for $m=3$. Our algorithm is based on a recursive scheduling approach where in each step we reduce the correlation in form of long chains. Our method adds to the rather short list of examples where hierarchies are actually useful to obtain better approximation algorithms.

We consider the classic problem of scheduling jobs with precedence constraints on identical machines to minimize makespan, in the presence of communication delays. In this setting, denoted by P | prec, c | Cmax, if two dependent jobs are scheduled on different machines, then at least c units of time must pass between their executions. Despite its relevance to many applications, this model remains one of the most poorly understood in scheduling theory. Even for a special case where an unlimited number of machines is available, the best known approximation ratio is 2/3·(c+1), whereas Graham's greedy list scheduling algorithm already gives a ( c+1) -approximation in that setting. An outstanding open problem in the top-10 list by Schuurman and Woeginger and its recent update by Bansal asks whether there exists a constant-factor approximation algorithm. In this work we give a polynomial-time O(logc·logm)-approximation algorithm for this problem, where m is the number of machines and c is the communication delay. Our approach is based on a Sherali-Adams lift of a linear programming relaxation and a randomized clustering of the semimetric space induced by this lift. The full version of this paper is available on arXiv.

A well-known problem in scheduling and approximation algorithms is the Santa Claus problem. Suppose that Santa Claus has a set of gifts, and he wants to distribute them among a set of children so that the least happy child is made as happy as possible. Here, the value that a child i has for a present j is of the form pij ϵ {0, pj}. A polynomial time algorithm by Annamalai et al. gives a 12.33-approximation and is based on a modification of Haxell's hypergraph matching argument. In this paper, we introduce a matroid version of the Santa Claus problem. Our algorithm is also based on Haxell's augmenting tree, but with the introduction of the matroid structure we solve a more general problem with cleaner methods. Our result can then be used as a blackbox to obtain a (4 + ϵ)-approximation for Santa Claus. This factor also compares against a natural, compact LP for Santa Claus.

The Matrix Spencer Conjecture asks whether given n symmetric matrices in ℝn×n with eigenvalues in [–1, 1] one can always find signs so that their signed sum has singular values bounded by . The standard approach in discrepancy requires proving that the convex body of all good fractional signings is large enough. However, this question has remained wide open due to the lack of tools to certify measure lower bounds for rather small non-polyhedral convex sets. A seminal result by Batson, Spielman and Srivastava from 2008 shows that any undirected graph admits a linear size spectral sparsifier. Again, one can define a convex body of all good fractional signings. We can indeed prove that this body is close to most of the Gaussian measure. This implies that a discrepancy algorithm by the second author can be used to sample a linear size sparsifer. In contrast to previous methods, we require only a logarithmic number of sampling phases.

We consider the bin packing problem with d different item sizes s i and item multiplicities a i , where all numbers are given in binary encoding. This problem formulation is also known as the one-dimensional cutting stock problem . In this work, we provide an algorithm that, for constant d , solves bin packing in polynomial time. This was an open problem for all d\ge 3 . In fact, for constant d our algorithm solves the following problem in polynomial time: Given two d -dimensional polytopes P and Q , find the smallest number of integer points in P whose sum lies in Q . Our approach also applies to high multiplicity scheduling problems in which the number of copies of each job type is given in binary encoding and each type comes with certain parameters such as release dates, processing times, and deadlines. We show that a variety of high multiplicity scheduling problems can be solved in polynomial time if the number of job types is constant.

One of the prominent open problems in combinatorics is the discrepancy of set systems where each element lies in at most t sets. The Beck-Fiala conjecture suggests that the right bound is , but for three decades the only known bound not depending on the size of set system has been O(t). Arguably we currently lack techniques for breaking that barrier. In this paper we introduce discrepancy bounds based on Fourier analysis. We demonstrate our method on random set systems. Suppose one has n elements and m sets containing each element independently with probability p. We prove that in the regime of n ≥ Θ(m2 log(m)), the discrepancy is at most 1 with high probability. Previously, a result of Ezra and Lovett gave a bound of O(1) under the stricter assumption that n ≫ mt.

For bin packing, the input consists of n items with sizes s1,…, sn ∊ [0,1] which have to be assigned to a minimum number of bins of size 1. Recently, the second author gave an LP-based polynomial time algorithm that employed techniques from discrepancy theory to find a solution using at most OPT + O(logOPT • loglog OPT) bins. In this paper, we build on the techniques of Rothvoss to present an approximation algorithm that has an additive gap of only O(log OPT) bins. This gap matches certain combinatorial lower bounds, and any further improvement would have to use more algebraic structure.

A popular method in combinatorial optimization is to express polytopes P , which may potentially have exponentially many facets, as solutions of linear programs that use few extra variables to reduce the number of constraints down to a polynomial. After two decades of standstill, recent years have brought amazing progress in showing lower bounds for the so-called extension complexity , which for a polytope P denotes the smallest number of inequalities necessary to describe a higher-dimensional polytope Q that can be linearly projected on P . However, the central question in this field remained wide open: can the perfect matching polytope be written as an LP with polynomially many constraints? We answer this question negatively. In fact, the extension complexity of the perfect matching polytope in a complete n -node graph is 2 Ω ( n ) . By a known reduction, this also improves the lower bound on the extension complexity for the TSP polytope from 2 Ω (√ n ) to 2 Ω ( n ) .

A classical theorem of Spencer shows that any set system with $n$ sets and $n$ elements admits a coloring of discrepancy $O(\sqrt{n})$. Recent exciting work of Bansal, Lovett, and Meka shows that such colorings can be found in polynomial time. In fact, the Lovett--Meka algorithm finds a half integral point in any “large enough” polytope. However, their algorithm crucially relies on the facet structure and does not apply to general convex sets. We show that for any symmetric convex set $K$ with Gaussian measure at least $e^{-n/500}$, the following algorithm finds a point $y \in K \cap [-1,1]^n$ with $\Omega(n)$ coordinates in $\pm 1$: (1) take a random Gaussian vector $x$; (2) compute the point $y$ in $K \cap [-1,1]^n$ that is closest to $x$; (3) return $y$. This provides another truly constructive proof of Spencer's theorem and the first constructive proof of a theorem of Gluskin and Giannopoulos.

In a classical problem in scheduling, one has n unit size jobs with a precedence order and the goal is to find a schedule of those jobs on m identical machines as to minimize the makespan. It is one of the remaining four open problems from the book of Garey & Johnson whether or not this problem is NP-hard for m=3.

In the highway problem, we are given an $n$-edge path graph (the highway), and a set of paths (the drivers), each one with its own budget. For a given assignment of edge weights (the tolls), the highway owner collects from each driver the weight of the associated path, when it does not exceed the budget of the driver, and zero otherwise. The goal is to choose weights so as to maximize the profit. A lot of research has been devoted to this apparently simple problem. The highway problem was shown to be strongly $\mathbf{NP}$-hard only recently [K. M. Elbassioni et al., in Proceedings of the International Symposium on Algorithmic Game Theory (SAGT), 2009, pp. 275--286]. The best-known approximation is $O(\log n/\log\log n)$ [I. Gamzu and D. Segev, in Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), 2010, pp. 582--593], which improves on the previous best $O(\log n)$ approximation [M.-F. Balcan and A. Blum, in Proceedings of the ACM Conference on Electronic Commerce, 2006, pp. 29--35]. Better approximations are known for a number of special cases. Finding a constant (or better!) approximation algorithm for the general case is a challenging open problem. In this paper we present a polynomial-time approximation scheme (PTAS) for the highway problem, hence greatly improving our understanding of the complexity status of this problem. Our result is based on a novel randomized dissection approach, which has some points in common with Arora's quadtree dissection for Euclidean network design [S. Arora, J. ACM, 45 (1998), pp. 753--782]. The basic idea is to enclose the highway in a bounding path, such that both the size of the bounding path and the position of the highway in it are random variables. Then we consider a recursive $O(1)$-ary dissection of the bounding path, in subpaths of uniform optimal weight. Since the optimal weights are unknown, we construct the dissection in a bottom-up fashion via dynamic programming, while computing the approximate solution at the same time. Our algorithm can be easily derandomized. The same basic approach also provides PTASs for two generalizations of the problem: the tollbooth problem with a constant number of leaves and the maximum-feasibility subsystem problem on interval matrices. In both cases the previous best approximation factors are polylogarithmic [I. Gamzu and D. Segev, in Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), 2010, pp. 582--593; K. M. Elbassioni et al., in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009, pp. 1210--1219].

For bin packing, the input consists of $n$ items with sizes $s_1,\ldots,s_n \in [0,1]$ which have to be assigned to a minimum number of bins of size 1. The seminal Karmarkar--Karp algorithm from 1982 produces a solution with at most $OPT + O(\log^2 OPT)$ bins. We provide the first improvement in over three decades and show that one can find a solution of cost $OPT + O(\log OPT \cdot \log \log OPT)$ in polynomial time. This is achieved by rounding a fractional solution to the Gilmore--Gomory LP relaxation using the partial coloring method from discrepancy theory. The result is constructive via the algorithms of Bansal and Lovett--Meka.

A classical theorem of Spencer shows that any set system with n sets and n elements admits a coloring of discrepancy O(√n). Recent exciting work of Bansal, Lovett and Meka shows that such colorings can be found in polynomial time. In fact, the Lovett-Meka algorithm finds a half integral point in any "large enough" polytope. However, their algorithm crucially relies on the facet structure and does not apply to general convex sets. We show that for any symmetric convex set K with measure at least e -- n/500, the following algorithm finds a point y ∈ K ∩ [ -- 1, 1]n with Ω(n) coordinates in ±1: (1) take a random Gaussian vector x, (2) compute the point y in K ∩ [ -- 1, 1]n that is closest to x. (3) return y. This provides another truly constructive proof of Spencer's theorem and the first constructive proof of a Theorem of Giannopoulos.

We consider the bin packing problem with d different item sizes si and item multiplicities ai, where all numbers are given in binary encoding. This problem formulation is also known as the 1-dimensional cutting stock problem. In this work, we provide an algorithm which, for constant d, solves bin packing in polynomial time. This was an open problem for all d ≥ 3. In fact, for constant d our algorithm solves the following problem in polynomial time: given two d-dimensional polytopes P and Q, find the smallest number of integer points in P whose sum lies in Q. Our approach also applies to high multiplicity scheduling problems in which the number of copies of each job type is given in binary encoding and each type comes with certain parameters such as release dates, processing times and deadlines. We show that a variety of high multiplicity scheduling problems can be solved in polynomial time if the number of job types is constant.

A popular method in combinatorial optimization is to express polytopes P, which may potentially have exponentially many facets, as solutions of linear programs that use few extra variables to reduce the number of constraints down to a polynomial. After two decades of standstill, recent years have brought amazing progress in showing lower bounds for the so called extension complexity, which for a polytope P denotes the smallest number of inequalities necessary to describe a higher dimensional polytope Q that can be linearly projected on P.

For bin packing, the input consists of n items with sizes between 0 and 1, which have to be assigned to a minimum number of bins of size 1. The seminal Karmarkar-Karp algorithm from '82 produces a solution with at most OPT + O(log2 OPT) bins. We provide the first improvement in now 3 decades and show that one can find a solution of cost OPT + O(log OPT · log log OPT) in polynomial time. This is achieved by rounding a fractional solution to the Gilmore-Gomory LP relaxation using the Entropy Method from discrepancy theory. The result is constructive via algorithms of Bansal and Lovett-Meka.

The Steiner tree problem is one of the most fundamental NP -hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for this problem was improved from 2 to 1.55 [Robins and Zelikovsky 2005]. All these algorithms are purely combinatorial. A long-standing open problem is whether there is an LP relaxation of Steiner tree with integrality gap smaller than 2 [Rajagopalan and Vazirani 1999]. In this article we present an LP-based approximation algorithm for Steiner tree with an improved approximation factor. Our algorithm is based on a, seemingly novel, iterative randomized rounding technique. We consider an LP relaxation of the problem, which is based on the notion of directed components. We sample one component with probability proportional to the value of the associated variable in a fractional solution: the sampled component is contracted and the LP is updated consequently. We iterate this process until all terminals are connected. Our algorithm delivers a solution of cost at most ln(4) + ε < 1.39 times the cost of an optimal Steiner tree. The algorithm can be derandomized using the method of limited independence. As a by-product of our analysis, we show that the integrality gap of our LP is at most 1.55, hence answering the mentioned open question.

A coloring of a hypergraph's vertices is polychromatic if every hyperedge contains at least one vertex of each color; the polychromatic number is the maximum number of colors in such a coloring. Its dual, the cover-decomposition number, is the maximum number of disjoint hyperedge-covers. In geometric hypergraphs, there is extensive work on lower-bounding these numbers in terms of their trivial upper bounds (minimum hyperedge size and degree); our goal here is to broaden the study beyond geometric settings. We obtain algorithms yielding near-tight bounds for three families of hypergraphs: bounded hyperedge size, paths in trees, and bounded Vapnik--Chervonenkis (VC)-dimension. This reveals that discrepancy theory and iterated linear program relaxation are useful for cover-decomposition. Finally, we discuss the generalization of cover-decomposition to sensor cover.

A well-studied special case of bin packing is the 3-partition problem , where n items of size > 1/4 have to be packed in a minimum number of bins of capacity one. The famous Karmarkar-Karp algorithm transforms a fractional solution of a suitable LP relaxation for this problem into an integral solution that requires at most O (log n ) additional bins. The three-permutations-problem of Beck is the following. Given any three permutations on n symbols, color the symbols red and blue, such that in any interval of any of those permutations, the number of red and blue symbols is roughly the same. The necessary difference is called the discrepancy . We establish a surprising connection between bin packing and Beck’s problem: The additive integrality gap of the 3-partition linear programming relaxation can be bounded by the discrepancy of three permutations. This connection yields an alternative method to establish an O (log n ) bound on the additive integrality gap of the 3-partition. Conversely, making use of a recent example of three permutations, for which a discrepancy of Ω(log n ) is necessary, we prove the following: The O (log 2 n ) upper bound on the additive gap for bin packing with arbitrary item sizes cannot be improved by any technique that is based on rounding up items. This lower bound holds for a large class of algorithms including the Karmarkar-Karp procedure.

Let A be a matrix, c be any linear objective function and x be a fractional vector, say an LP solution to some discrete optimization problem. Then a recurring task in theoretical computer science (and in approximation algorithms in particular) is to obtain an integral vector y such that Ax ≈ Ay and cTy exceeds cTx by only a moderate factor. We give a new randomized rounding procedure for this task, provided that A has bounded Δ-approximate entropy. This property means that for uniformly chosen random signs χ(j) ∊ {±1} on any subset of the columns, the outcome Aχ can be approximately described using at most bits in expectation (with m being the number of selected columns). To achieve this result, we modify well-known techniques from the field of discrepancy theory, especially we rely on Beck's entropy method, which to the best of our knowledge has never been used before in the context of approximation algorithms. Our result can be made constructive using the Bansal framework based on semidefinite programming. We demonstrate the versatility of our procedure by rounding fractional solutions to column-based linear programs for some generalizations of Bin Packing. For example we obtain a polynomial time OPT + O(log2 OPT) approximation for Bin Packing With Rejection and the first AFPTAS for the Train Delivery problem.

Until recently, LP relaxations have only played a very limited role in the design of approximation algorithms for the Steiner tree problem. In particular, no (efficiently solvable) Steiner tree relaxation was known to have an integrality gap bounded away from 2, before Byrka et al. [3] showed an upper bound of ~1.55 of a hypergraphic LP relaxation and presented a ln(4)+ε ~1.39 approximation based on this relaxation. Interestingly, even though their approach is LP based, they do not compare the solution produced against the LP value. We take a fresh look at hypergraphic LP relaxations for the Steiner tree problem---one that heavily exploits methods and results from the theory of matroids and submodular functions---which leads to stronger integrality gaps, faster algorithms, and a variety of structural insights of independent interest. More precisely, along the lines of the algorithm of Byrka et al.[3], we present a deterministic ln(4)+ε approximation that compares against the LP value and therefore proves a matching ln(4) upper bound on the integrality gap of hypergraphic relaxations.

A well studied special case of bin packing is the 3-partition problem, where n items of size > ¼ have to be packed in a minimum number of bins of capacity one. The famous Karmarkar-Karp algorithm transforms a fractional solution of a suitable LP relaxation for this problem into an integral solution that requires at most O(log n) additional bins. The three-permutations-conjecture of Beck is the following. Given any 3 permutations on n symbols, one can color the symbols red and blue, such that in any interval of any of those permutations, the number of red and blue symbols differs only by a constant. Beck's conjecture is well known in the field of discrepancy theory. We establish a surprising connection between bin packing and Beck's conjecture: If the latter holds true, then the additive integrality gap of the 3-partition linear programming relaxation is bounded by a constant.

In the highway problem, we are given an n-edge line graph (the highway), and a set of paths (the drivers), each one with its own budget. For a given assignment of edge weights (the tolls), the highway owner collects from each driver the weight of the associated path, when it does not exceed the budget of the driver, and zero otherwise. The goal is choosing weights so as to maximize the profit. A lot of research has been devoted to this apparently simple problem. The highway problem was shown to be strongly NP-hard only recently [Elbassioni, Raman, Ray, Sitters-'09]. The best-known approximation is O(log n/log log n) [Gamzu, Segev-'10], which improves on the previous-best O(log n) approximation [Balcan, Blum-'06]. Better approximations are known for a number of special cases. Finding a constant (or better!) approximation algorithm for the general case is a challenging open problem. In this paper we present a PTAS for the highway problem, hence closing the complexity status of the problem. Our result is based on a novel randomized dissection approach, which has some points in common with Arora's quadtree dissection for Euclidean network design [Arora-'98]. The basic idea is enclosing the highway in a bounding path, such that both the size of the bounding path and the position of the highway in it are random variables. Then we consider a recursive O(1)-ary dissection of the bounding path, in sub-paths of uniform optimal weight. Since the optimal weights are unknown, we construct the dissection in a bottom-up fashion via dynamic programming, while computing the approximate solution at the same time. Our algorithm can be easily derandomized. The same basic approach provides PTASs also for two generalizations of the problem: the tollbooth problem with a constant number of leaves and the maximum-feasibility subsystem problem on interval matrices. In both cases the previous best approximation factors are polylogarithmic [Gamzu, Segev-'10, Elbassioni, Raman, Ray, Sitters-'09].

In the synchronous periodic task model, a set τ1, …, τn of tasks is given, each releasing jobs of running time ci with relative deadline di, at each integer multiple of the period pi. It is a classical result that Earliest Deadline First (EDF) is an optimal preemptive uniprocessor scheduling policy. For constrained deadlines, i.e. di ≤ pi, the EDF-schedule is feasible if and only if Though an enormous amount of literature deals with this topic, the complexity status of this test has remained unknown. We prove that testing EDF-schedulability of such a task system is (weakly) coNP-hard. This solves Problem 2 from the survey “Open Problems in Real-time Scheduling” by Baruah & Pruhs. The hardness result is achieved by applying recent results on inapproximability of Diophantine approximation.

The Steiner tree problem is one of the most fundamental NP-hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for this problem was improved from 2 to the current best 1.55 [Robins,Zelikovsky-SIDMA'05]. All these algorithms are purely combinatorial. A long-standing open problem is whether there is an LP-relaxation for Steiner tree with integrality gap smaller than 2 [Vazirani,Rajagopalan-SODA'99]. In this paper we improve the approximation factor for Steiner tree, developing an LP-based approximation algorithm. Our algorithm is based on a, seemingly novel, iterative randomized rounding technique. We consider a directed-component cut relaxation for the k-restricted Steiner tree problem. We sample one of these components with probability proportional to the value of the associated variable in the optimal fractional solution and contract it. We iterate this process for a proper number of times and finally output the sampled components together with a minimum-cost terminal spanning tree in the remaining graph. Our algorithm delivers a solution of cost at most ln(4) times the cost of an optimal k-restricted Steiner tree. This directly implies a ln(4)+ε<1.39 approximation for Steiner tree. As a byproduct of our analysis, we show that the integrality gap of our LP is at most $1.55$, hence answering to the mentioned open question. This might have consequences for a number of related problems.

We investigate the diameter of a natural abstraction of the 1-skeleton of polyhedra. Although this abstraction is simpler than other abstractions that were previously studied in the literature, the best upper bounds on the diameter of polyhedra continue to hold here. On the other hand, we show that this abstraction has its limits by providing a superlinear lower bound.

We show that response time computation for Rate-monotonic,preemptive scheduling of periodic tasks is NP-hard under Turingreductions. More precisely, we show that the response time of a taskcannot be approximated within any constant factor, unless P=NP.