Recent concurrent work by Dupré la Tour and Fujii and by Hollender, Manurangsi, Meka, and Suksompong [ITCS'26] introduced a generalization of classical discrepancy theory to non-additive functions, motivated by applications in fair division. As many classical techniques from discrepancy theory seem to fail in this setting, including linear algebraic methods like the Beck-Fiala Theorem [Discrete Appl. Math '81], it remains widely open whether comparable non-additive bounds can be achieved. Towards a better understanding of non-additive discrepancy, we study coverage functions in a sparse setting comparable to the classical Beck-Fiala Theorem. Our setting generalizes the additive Beck-Fiala setting, rank functions of partition matroids, and edge coverage in graphs. More precisely, assuming each of the n items covers only t elements across all functions, we prove a constructive discrepancy bound that is polynomial in t, the number of colors k, and log n.

We study a problem related to submodular function optimization and the exact matching problem for which we show a rather peculiar status: its natural LP-relaxation can have fractional optimal vertices, but there is always also an optimal integral vertex, which we can also compute in polynomial time. More specifically, we consider the multiplicative assignment problem with upgrades in which we are given a set of customers and suppliers and we seek to assign each customer to a different supplier. Each customer has a demand and each supplier has a regular and an upgraded cost for each unit demand provided to the respective assigned client. Our goal is to upgrade at most k suppliers and to compute an assignment in order to minimize the total resulting cost. This can be cast as the problem to compute an optimal matching in a bipartite graph with the additional constraint that we must select k edges from a certain group of edges, similar to selecting k red edges in the exact matching problem. Also, selecting the suppliers to be upgraded corresponds to maximizing a submodular set function under a cardinality constraint. Our result yields an efficient LP-based algorithm to solve our problem optimally. In addition, we also provide a purely strongly polynomial-time algorithm for it. As an application, we obtain exact algorithms for the upgrading variant of the problem to schedule jobs on identical or uniformly related machines in order to minimize their sum of completion times, i.e., where we may upgrade up to k jobs to reduce their respective processing times.

We study the general scheduling problem (GSP) which generalizes and unifies several well-studied preemptive single-machine scheduling problems, such as weighted flow time, weighted sum of completion time, and minimizing the total weight of tardy jobs. We are given a set of jobs with their processing times and release times and seek to compute a (possibly preemptive) schedule for them on one machine. Each job incurs a cost that depends on its completion time in the computed schedule, as given by a separate job-dependent cost function for each job, and our objective is to minimize the total resulting cost of all jobs. The best known result for GSP is a polynomial time \(O(\log \log P)\)-approximation algorithm [Bansal and Pruhs, FOCS 2010, SICOMP 2014].

We show that under mild assumptions for a problem whose solutions admit a dynamic programming-like recurrence relation, we can still find a solution under additional packing constraints, which need to be satisfied approximately. The number of additional constraints can be very large, e.g., polynomial in the problem size. Technically, we reinterpret the dynamic programming subproblems and their solutions as a network design problem. Inspired by techniques from, e.g., the Directed Steiner Tree problem, we construct a strong LP relaxation, on which we then apply randomized rounding. Our approximation guarantees on the packing constraints have roughly the form of a (nє polylog n)-approximation in time nO(1/є), for any є > 0. By setting є=loglogn/logn, we obtain a polylogarithmic approximation in quasi-polynomial time, or by setting є as a constant, an nє-approximation in polynomial time.

We consider ordinal scheduling on identical parallel machines with cardinality constraints. That is, a parameter k=1 is given such that no machine can contain more than k jobs. The objective is to assign the jobs to machines such that the makespan is minimized. In the ordinal setting, jobs are presented one by one and it is known that they arrive sorted by non-increasing sizes, but the specific sizes become known only after termination of the algorithm. An ordinal algorithm is compared to an optimal offline algorithm that knows all sizes, but it can also assign at most k jobs to each machine. Several simple algorithms achieve a competitive ratio of 2. In this work, we improve this ratio using a carefully designed algorithm.

An important objective function in the scheduling literature is to minimize the sum of weighted flow times. We are given a set of jobs, where each job is characterized by a release time, a processing time, and a weight. Our goal is to find a preemptive schedule on a single machine that minimizes the sum of the weighted flow times of the jobs, where the flow time of a job is the time between its completion time and its release time. In their breakthrough result, Batra, Garg, and Kumar [FOCS 2018] found the first pseudopolynomial-time constant-factor approximation algorithm for the problem, which was turned into a polynomial-time algorithm by Feige, Kulkarni, and Li [SODA 2019]. The resulting approximation ratio is a (not explicitly stated) constant which is at least 10,000. In this article, we improve this to a PTAS. 1 The algorithm by Batra et al. reduces the problem to Demand MultiCut on trees and solves the resulting instances via LP-rounding and a dynamic program. Instead, we first reduce the problem to a (different) geometric problem while losing only a factor \(1 + \varepsilon\) , and then solve its resulting instances exactly by a dynamic program. In particular, our reduction ensures certain structural properties, due to which we do not need LP-rounding techniques.

We consider the Stochastic Boolean Function Evaluation (SBFE) problem in the well-studied case of $k$-of-$n$ functions: There are independent Boolean random variables $x_1,\dots,x_n$ where each variable $i$ has a known probability $p_i$ of taking value $1$, and a known cost $c_i$ that can be paid to find out its value. The value of the function is $1$ iff there are at least $k$ $1$s among the variables. The goal is to efficiently compute a strategy that, at minimum expected cost, tests the variables until the function value is determined. While an elegant polynomial-time exact algorithm is known when tests can be made adaptively, we focus on the non-adaptive variant, for which much less is known. First, we show a clean and tight lower bound of $2$ on the adaptivity gap, i.e., the worst-case multiplicative loss in the objective function caused by disallowing adaptivity, of the problem. This improves the tight lower bound of $3/2$ for the unit-cost variant. Second, we give a PTAS for computing the best non-adaptive strategy in the unit-cost case, the first PTAS for an SBFE problem. At the core, our scheme establishes a novel notion of two-sided dominance (w.r.t. the optimal solution) by guessing so-called milestone tests for a set of carefully chosen buckets of tests. To turn this technique into a polynomial-time algorithm, we use a decomposition approach paired with a random-shift argument. In fact, our PTAS extends to the class of arbitrary symmetric Boolean functions, which are Boolean functions whose value only depends on the number of $1$s among the input variables.

Given $n$ jobs with processing times $p_1,\dotsc,p_n\in\mathbb N$ and $m\le n$ machines with speeds $s_1,\dotsc,s_m\in\mathbb N$ our goal is to allocate the jobs to machines minimizing the makespan. We present an algorithm that solves the problem in time $p_{\max}^{O(d)} n^{O(1)}$, where $p_{\max}$ is the maximum processing time and $d\le p_{\max}$ is the number of distinct processing times. This is essentially the best possible due to a lower bound based on the exponential time hypothesis (ETH). Our result improves over prior works that had a quadratic term in $d$ in the exponent and answers an open question by Koutecký and Zink. The algorithm is based on integer programming techniques combined with novel ideas based on modular arithmetic. They can also be implemented efficiently for the more compact high-multiplicity instance encoding.

We present a dependent randomized rounding scheme, which rounds fractional solutions to integral solutions satisfying certain hard constraints on the output while preserving Chernoff-like concentration properties. In contrast to previous dependent rounding schemes, our algorithm guarantees that the cost of the rounded integral solution does not exceed that of the fractional solution. Our algorithm works for a class of assignment problems with restrictions similar to those of prior works. In a non-trivial combination of our general result with a classical approach from Shmoys and Tardos [Math. Programm.'93] and more recent linear programming techniques developed for the restricted assignment variant by Bansal, Sviridenko [STOC'06] and Davies, Rothvoss, Zhang [SODA'20], we derive a O(log n)-approximation algorithm for the Budgeted Santa Claus Problem. In this new variant, the goal is to allocate resources with different values to players, maximizing the minimum value a player receives, and satisfying a budget constraint on player-resource allocation costs.

Integer Linear Programming with n binary variables and m many 0/1-constraints can be solved in time 2^Õ(m²) poly(n) and it is open whether the dependence on m is optimal. Several seemingly unrelated problems, which include variants of Closest String, Discrepancy Minimization, Set Cover, and Set Packing, can be modelled as Integer Linear Programming with 0/1 constraints to obtain algorithms with the same running time for a natural parameter m in each of the problems. Our main result establishes through fine-grained reductions that these problems are equivalent, meaning that a 2^O(m^{2-ε}) poly(n) algorithm with ε > 0 for one of them implies such an algorithm for all of them. In the setting above, one can alternatively obtain an n^O(m) time algorithm for Integer Linear Programming using a straightforward dynamic programming approach, which can be more efficient if n is relatively small (e.g., subexponential in m). We show that this can be improved to {n'}^O(m) + O(nm), where n' is the number of distinct (i.e., non-symmetric) variables. This dominates both of the aforementioned running times.

We consider the problem of allocating indivisible resources to players so as to maximize the minimum total value any player receives. This problem is sometimes dubbed the Santa Claus problem and its different variants have been subject to extensive research towards approximation algorithms over the past two decades.

No abstract available.

We consider the problem of finding a basis of a matroid with weight exactly equal to a given target. Here weights can be discrete values from$\{-\Delta,\ \ldots,\ \Delta\}$or more generally m-dimensional vectors of such discrete values. We resolve the parameterized complexity completely, by presenting an FPT algorithm parameterized by$\Delta$and$m$for arbitrary matroids. Prior to our work, no such algorithms were known even when weights are in$\{0,1\}$, or arbitrary$\Delta$and$m=1$. Our main technical contributions are new proximity and sensitivity bounds for matroid problems, independent of the number of elements. These bounds imply FPT algorithms via matroid intersection.

In this paper we study the relation of two fundamental problems in scheduling and fair allocation: makespan minimization on unrelated parallel machines and max-min fair allocation, also known as the Santa Claus problem. For both of these problems the best approximation factor is a notorious open question; more precisely, whether there is a better-than-2 approximation for the former problem and whether there is a constant approximation for the latter.

The starting point of this paper is the problem of scheduling n jobs with processing times and due dates on a single machine so as to minimize the total processing time of tardy jobs, i.e., 1 || ΣpjUj. This problem was identified by Bringmann et al. (Algorithmica 2022) as a natural subquadratic-time special case of the classic 1 || Σ wjUj problem, which likely requires time quadratic in the total processing time P, because of a fine-grained lower bound. Bringmann et al. obtain their Õ(P7/4) time scheduling algorithm through a new variant of convolution, dubbed Max-Min Skewed Convolution, which they solve in Õ(n7/4) time. Our main technical contribution is a faster and simpler convolution algorithm running in Õ(n5/3) time. It implies an Õ(P5/3) time algorithm for 11 | ΣpjUj, but may also be of independent interest.

An important objective function in the scheduling literature is to minimize the sum of weighted flow times. We are given a set of jobs, where each job is characterized by a release time, a processing time, and a weight. Our goal is to find a preemptive schedule on a single machine that minimizes the sum of the weighted flow times of the jobs, where the flow time of a job is the time between its completion time and its release time. The currently best known polynomial time algorithm for the problem is a (2+є)-approximation by Rohwedder and Wiese [STOC 2021], which builds on the prior break-through result by Batra, Garg, and Kumar [FOCS 2018] who found the first pseudo-polynomial time constant factor approximation algorithm for the problem, and on the result by Feige, Kulkarni, and Li [SODA 2019] who turned the latter into a polynomial time algorithm. However, it remains open whether the problem admits a PTAS.

We revisit the problem max-min degree arborescence, which was introduced by Bateni et al. [STOC’09] as a central special case of the general Santa Claus problem, which constitutes a notorious open question in approximation algorithms. In the former problem we are given a directed graph with sources and sinks and our goal is to find vertex disjoint arborescences rooted in the sources such that at each non-sink vertex of an arborescence the out-degree is at least k, where k is to be maximized. This problem is of particular interest, since it appears to capture much of the difficulty of the Santa Claus problem: (1) like in the Santa Claus problem the configuration LP has a large integrality gap in this case and (2) previous progress by Bateni et al. was quickly generalized to the Santa Claus problem (Chakrabarty et al. [FOCS’09]). These results remain the state-of-the-art both for the Santa Claus problem and for max-min degree arborescence and they yield a polylogarithmic approximation in quasi-polynomial time. We present an exponential improvement to this, a poly(loglogn)-approximation in quasi-polynomial time for the max-min degree arborescence problem. To the best of our knowledge, this is the first example of breaking the logarithmic barrier for a special case of the Santa Claus problem, where the configuration LP cannot be utilized. The main technical novelty of our result are locally good solutions: informally, we show that it suffices to find a poly(logn)-approximation that locally has stronger guarantees. We use a lift-and-project type of LP and randomized rounding, which were also used by Bateni et al., but unlike previous work we integrate careful pruning steps in the rounding. In the proof we extensively apply Lovász Local Lemma and a local search technique, both of which were previously used only in the context of the configuration LP.

Semi-online models where decisions may be revoked in a limited way have been studied extensively in the last years. A well-studied measure of the amount of decisions that can be revoked is the (constant) migration factor. When an object arrives, the decisions for objects of total size at most the migration factor times its size may be revoked. This means that a small object only leads to small changes. We extensively study the bin covering problem with migration in different scenarios. We develop algorithms both for the static case where only insertions are allowed, and for the dynamic case, where items may also depart. We also develop lower bounds for these scenarios both for amortized migration and for worst-case migration showing that our algorithms have nearly optimal migration factor and asymptotic competitive ratio. We therefore resolve the competitiveness of the bin covering problem with migration.

There is a long history of approximation schemes for the problem of scheduling jobs on identical machines to minimize the makespan. Such a scheme grants a (1 + ε)-approximation solution for every ε > 0, but the running time grows exponentially in 1/ε. For a long time, these schemes seemed like a purely theoretical concept. Even solving instances for moderate values of ε seemed completely illusional. In an effort to bridge theory and practice, we refine recent ILP techniques to develop the fastest known approximation scheme for this problem. An implementation of this algorithm reaches values of ε lower than 2/11 ≈ 18.2% within a reasonable timespan. This is the approximation guarantee of MULTIFIT, which, to the best of our knowledge, has the best proven guarantee of any non-scheme algorithm.

Makespan minimization on parallel identical machines is a classical and intensively studied problem in scheduling, and a classic example for online algorithm analysis with Graham’s famous list scheduling algorithm dating back to the 1960s. In this problem, jobs arrive over a list and upon an arrival, the algorithm needs to assign the job to a machine. The goal is to minimize the makespan, that is, the maximum machine load. In this paper, we consider the variant with an additional cardinality constraint: The algorithm may assign at most k jobs to each machine where k is part of the input. While the offline (strongly NP-hard) variant of cardinality constrained scheduling is well understood and an EPTAS exists here, no non-trivial results are known for the online variant. We fill this gap by making a comprehensive study of various different online models. First, we show that there is a constant competitive algorithm for the problem and further, present a lower bound of 2 on the competitive ratio of any online algorithm. Motivated by the lower bound, we consider a semi-online variant where upon arrival of a job of size p, we are allowed to migrate jobs of total size at most a constant times p. This constant is called the migration factor of the algorithm. Algorithms with small migration factors are a common approach to bridge the performance of online algorithms and offline algorithms. One can obtain algorithms with a constant migration factor by rounding the size of each incoming job and then applying an ordinal algorithm to the resulting rounded instance. With this in mind, we also consider the framework of ordinal algorithms and characterize the competitive ratio that can be achieved using the aforementioned approaches. More specifically, we show that in both cases, one can get a competitive ratio that is strictly lower than 2, which is the bound from the standard online setting. On the other hand, we prove that no PTAS is possible.

We relate discrepancy theory with the classic scheduling problems of minimizing max flow time and total flow time on unrelated machines. Specifically, we give a general reduction that allows us to transfer discrepancy bounds in the prefix Beck-Fiala (bounded ℓ1-norm) setting to bounds on the flow time of an optimal schedule. Combining our reduction with a deep result proved by Banaszczyk via convex geometry, give guarantees of O(√logn) and O(√logn logP) for max flow time and total flow time, respectively, improving upon the previous best guarantees of O(logn) and O(logn logP). Apart from the improved guarantees, the reduction motivates seemingly easy versions of prefix discrepancy questions: any constant bound on prefix Beck-Fiala where vectors have sparsity two (sparsity one being trivial) would already yield tight guarantees for both max flow time and total flow time. While known techniques solve this case when the entries take values in {−1,0,1}, we show that they are unlikely to transfer to the more general 2-sparse case of bounded ℓ1-norm.

Knapsack and Subset Sum are fundamental NP-hard problems in combinatorial optimization. Recently there has been a growing interest in understanding the best possible pseudopolynomial running times for these problems with respect to various parameters. In this paper we focus on the maximum item size s and the maximum item value v. We give algorithms that run in time O(n + s³) and O(n + v³) for the Knapsack problem, and in time Õ(n + s^{5/3}) for the Subset Sum problem. Our algorithms work for the more general problem variants with multiplicities, where each input item comes with a (binary encoded) multiplicity, which succinctly describes how many times the item appears in the instance. In these variants n denotes the (possibly much smaller) number of distinct items. Our results follow from combining and optimizing several diverse lines of research, notably proximity arguments for integer programming due to Eisenbrand and Weismantel (TALG 2019), fast structured (min,+)-convolution by Kellerer and Pferschy (J. Comb. Optim. 2004), and additive combinatorics methods originating from Galil and Margalit (SICOMP 1991).

The submodular Santa Claus problem was introduced in a seminal work by Goemans, Harvey, Iwata, and Mirrokni (SODA'09) as an application of their structural result. In the mentioned problem n unsplittable resources have to be assigned to m players, each with a monotone submodular utility function f_i. The goal is to maximize min_i f_i(S_i) where S₁,...,S_m is a partition of the resources. The result by Goemans et al. implies a polynomial time O(n^{1/2 +ε})-approximation algorithm. Since then progress on this problem was limited to the linear case, that is, all f_i are linear functions. In particular, a line of research has shown that there is a polynomial time constant approximation algorithm for linear valuation functions in the restricted assignment case. This is the special case where each player is given a set of desired resources Γ_i and the individual valuation functions are defined as f_i(S) = f(S ∩ Γ_i) for a global linear function f. This can also be interpreted as maximizing min_i f(S_i) with additional assignment restrictions, i.e., resources can only be assigned to certain players. In this paper we make comparable progress for the submodular variant: If f is a monotone submodular function, we can in polynomial time compute an O(log log(n))-approximate solution.

In this paper we introduce the concept of additive approximation schemes and apply it to load balancing problems. Additive approximation schemes aim to find a solution with an absolute error in the objective of at most $εh$ for some suitable parameter $h$. In the case that the parameter $h$ provides a lower bound an additive approximation scheme implies a standard multiplicative approximation scheme and can be much stronger when $h \ll$ OPT. On the other hand, when no PTAS exists (or is unlikely to exist), additive approximation schemes can provide a different notion for approximation. We consider the problem of assigning jobs to identical machines with lower and upper bounds for the loads of the machines. This setting generalizes problems like makespan minimization, the Santa Claus problem (on identical machines), and the envy-minimizing Santa Claus problem. For the last problem, in which the objective is to minimize the difference between the maximum and minimum load, the optimal objective value may be zero and hence it is NP-hard to obtain any multiplicative approximation guarantee. For this class of problems we present additive approximation schemes for $h = p_{\max}$, the maximum processing time of the jobs. Our technical contribution is two-fold. First, we introduce a new relaxation based on integrally assigning slots to machines and fractionally assigning jobs to the slots (the slot-MILP). We identify structural properties of (near-)optimal solutions of the slot-MILP, which allow us to solve it efficiently, assuming that there are $O(1)$ different lower and upper bounds on the machine loads (which is the relevant setting for the three problems mentioned above). The second technical contribution is a local-search based algorithm which rounds a solution to the slot-MILP introducing an additive error on the target load intervals of at most $ε\cdot p_{\max}$.

We consider integer and linear programming problems for which the linear constraints exhibit a (recursive) block-structure: The problem decomposes into independent and efficiently solvable sub-problems if a small number of constraints is deleted. A prominent example are n-fold integer programming problems and their generalizations which have received considerable attention in the recent literature. The previously known algorithms for these problems are based on the augmentation framework, a tailored integer programming variant of local search. In this paper we propose a different approach. Our algorithm relies on parametric search and a new proximity bound. We show that block-structured linear programming can be solved efficiently via an adaptation of a parametric search framework by Norton, Plotkin, and Tardos in combination with Megiddo's multidimensional search technique. This also forms a subroutine of our algorithm for the integer programming case by solving a strong relaxation of it. Then we show that, for any given optimal vertex solution of this relaxation, there is an optimal integer solution within ℓ1-distance independent of the dimension of the problem. This in turn allows us to find an optimal integer solution efficiently. We apply our techniques to integer and linear programming with n-fold structure or bounded dual treedepth, two benchmark problems in this field. We obtain the first algorithms for these cases that are both near-linear in the dimension of the problem and strongly polynomial. Moreover, unlike the augmentation algorithms, our approach is highly parallelizable.

Weighted flow time is a fundamental and very well-studied objective function in scheduling. In this paper, we study the setting of a single machine with preemptions.

In this paper, we study streaming and online algorithms in the context of randomness in the input. For several problems, a random order of the input sequence---as opposed to the worst-case order---appears to be a necessary evil in order to prove satisfying guarantees. However, algorithmic techniques that work under this assumption tend to be vulnerable to even small changes in the distribution. For this reason, we propose a new \emph{adversarial injections} model, in which the input is ordered randomly, but an adversary may inject misleading elements at arbitrary positions. We believe that studying algorithms under this much weaker assumption can lead to new insights and, in particular, more robust algorithms. We investigate two classical combinatorial-optimization problems in this model: Maximum matching and cardinality constrained monotone submodular function maximization. Our main technical contribution is a novel streaming algorithm for the latter that computes a $0.55$-approximation. While the algorithm itself is clean and simple, an involved analysis shows that it emulates a subdivision of the input stream which can be used to greatly limit the power of the adversary.

As power management has become a primary concern in modern data centers, computing resources are being scaled dynamically to minimize energy consumption. We initiate the study of a variant of the classic online speed scaling problem, in which machine learning predictions about the future can be integrated naturally. Inspired by recent work on learning-augmented online algorithms, we propose an algorithm which incorporates predictions in a black-box manner and outperforms any online algorithm if the accuracy is high, yet maintains provable guarantees if the prediction is very inaccurate. We provide both theoretical and experimental evidence to support our claims.

The Restricted Assignment problem is a prominent special case of Scheduling on Unrelated Parallel Machines. For the strongest known linear programming relaxation, the configuration LP, we improve the nonconstructive bound on its integrality gap from 1.9412 to 1.8334 and significantly simplify the proof. Then we give a constructive variant, yielding a 1.8334-approximation in quasi-polynomial time. This is the first quasi-polynomial algorithm for this problem improving on the long-standing approximation rate of 2.

We study an important case of integer linear programs (ILPs) of the form $\max\{c^Tx \ \vert\ \mathcal Ax = b, l \leq x \leq u,\, x \in \mathbb{Z}^{n t} \} $ with $n t$ variables and lower and upper bounds $\ell, u\in\mathbb Z^{nt}$. In $n$-fold ILPs nonzero entries only appear in the first $r$ rows of the matrix $\mathcal A$ and in small blocks of size $s\times t$ along the diagonal underneath. Despite this restriction, many optimization problems can be expressed in this form. It is known that $n$-fold ILPs are fixed-parameter tractable (FPT) regarding the parameters $s, r,$ and $\Delta$, where $\Delta$ is the greatest absolute value of any entry in $\mathcal A$. The state-of-the-art technique is a local search algorithm that subsequently moves in an improving direction where the number of iterations and the search for such an improving direction each take time $\Omega(n)$. This leads to a running time quadratic in $n$. We introduce a technique based on color coding which allows us to compute these improving directions in logarithmic time after a single initialization step. This yields an algorithm for $n$-fold ILPs with a running time that is near-linear in $nt$, the number of variables. More precisely, our algorithm runs in time $(rs\Delta)^{\mathcal{O}(r^2s + s^2)} L^2 nt \log^{\mathcal{O}(1)}(nt)$, where $L$ is the encoding length of the largest integer in the input. Further, in contrast to the algorithms in recent literature, we do not need to solve the LP relaxation in order to handle unbounded variables. Instead we give a structural lemma to introduce appropriate bounds. On the other hand, if we are given such an LP solution, the running time can be decreased by a factor of $L$.

Graph Balancing is the problem of orienting the edges of a weighted multigraph so as to minimize the maximum weighted in-degree. Since the introduction of the problem the best algorithm known achieves an approximation ratio of $1.75$ and it is based on rounding a linear program with this exact integrality gap. It is also known that there is no $(1.5 - ε)$-approximation algorithm, unless $\mathrm{P}=\mathrm{NP}$. Can we do better than $1.75$? We prove that a different LP formulation, the configuration LP, has a strictly smaller integrality gap. Graph Balancing was the last one in a group of related problems from literature, for which it was open whether the configuration LP is stronger than previous, simple LP relaxations. We base our proof on a local search approach that has been applied successfully to the more general Restricted Assignment problem, which in turn is a prominent special case of makespan minimization on unrelated machines. With a number of technical novelties we are able to obtain a bound of $1.749$ for the case of Graph Balancing. It is not clear whether the local search algorithm we present terminates in polynomial time, which means that the bound is non-constructive. However, it is a strong evidence that a better approximation algorithm is possible using the configuration LP and it allows the optimum to be estimated within a factor better than $1.75$. A particularly interesting aspect of our techniques is the way we handle small edges in the local search. We manage to exploit the configuration constraints enforced on small edges in the LP. This may be of interest to other problems such as Restricted Assignment as well.

Integer programs with a constant number of constraints are solvable in pseudo-polynomial time. We give a new algorithm with a better pseudo-polynomial running time than previous results. Moreover, we establish a strong connection to the problem (min, +)-convolution. (min, +)-convolution has a trivial quadratic time algorithm and it has been conjectured that this cannot be improved significantly. We show that further improvements to our pseudo-polynomial algorithm for any fixed number of constraints are equivalent to improvements for (min, +)-convolution. This is a strong evidence that our algorithm's running time is the best possible. We also present a faster specialized algorithm for testing feasibility of an integer program with few constraints and for this we also give a tight lower bound, which is based on the SETH.

We consider the classical problem of scheduling on unrelated machines. In this problem a set of jobs is to be distributed among a set of machines and the maximum load (makespan) is to be minimized. The processing time pij of a job j depends on the machine i it is assigned to. Lenstra, Shmoys and Tardos gave a polynomial time 2-approximation for this problem [8]. In this paper we focus on a prominent special case, the restricted assignment problem, in which pij ∊ {pj, ∞}. The configuration-LP is a linear programming relaxation for the restricted assignment problem. It was shown by Svensson that the multiplicative gap between integral and fractional solution, the integrality gap, is at most 2 – 1/17 ≈ 1.9412 [11]. In this paper we significantly simplify his proof and achieve a bound of 2 – 1/6 ≈ 1.8333. As a direct consequence this provides a polynomial (2 – 1/6 + ∊)-estimation algorithm for the restricted assignment problem by approximating the configuration-LP. The best lower bound known for the integrality gap is 1.5 and no estimation algorithm with a guarantee better than 1.5 exists unless P = NP.