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.

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 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.

We consider the problem of solving integer programs of the form $\min \{\,c^\intercal x\ \colon\ Ax=b, x\geq 0\}$, where $A$ is a multistage stochastic matrix in the following sense: the primal treedepth of $A$ is bounded by a parameter $d$, which means that the columns of $A$ can be organized into a rooted forest of depth at most $d$ so that columns not bound by the ancestor/descendant relation in the forest do not have non-zero entries in the same row. We give an algorithm that solves this problem in fixed-parameter time $f(d,\|A\|_{\infty})\cdot n\log^{O(2^d)} n$, where $f$ is a computable function and $n$ is the number of rows of $A$. The algorithm works in the strong model, where the running time only measures unit arithmetic operations on the input numbers and does not depend on their bitlength. This is the first fpt algorithm for multistage stochastic integer programming to achieve almost linear running time in the strong sense. For the case of two-stage stochastic integer programs, our algorithm works in time $2^{(2\|A\|_\infty)^{O(r(r+s))}}\cdot n\log^{O(rs)} n$. The algorithm can be also parallelized: we give an implementation in the PRAM model that achieves running time $f(d,\|A\|_{\infty})\cdot \log^{O(2^d)} n$ using $n$ processors. The main conceptual ingredient in our algorithms is a new proximity result for multistage stochastic integer programs. We prove that if we consider an integer program $P$, say with a constraint matrix $A$, then for every optimum solution to the linear relaxation of $P$ there exists an optimum (integral) solution to $P$ that lies, in the $\ell_{\infty}$-norm, within distance bounded by a function of $\|A\|_{\infty}$ and the primal treedepth of $A$. On the way to achieve this result, we prove a generalization and considerable improvement of a structural result of Klein for multistage stochastic integer programs.

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.

We show that a constant factor approximation of the shortest and closest lattice vector problem w.r.t. any 𝓁_p-norm can be computed in time 2^{(0.802 +ε) n}. This matches the currently fastest constant factor approximation algorithm for the shortest vector problem w.r.t. 𝓁₂. To obtain our result, we combine the latter algorithm w.r.t. 𝓁₂ with geometric insights related to coverings.

We consider integer programming problems max {c^Tx : A x = b, l <= x <= u, x in Z^{nt}} where A has a (recursive) block-structure generalizing n-fold integer programs which recently received considerable attention in the literature. An n-fold IP is an integer program where A consists of n repetitions of submatrices A in Z^{r × t} on the top horizontal part and n repetitions of a matrix B in Z^{s × t} on the diagonal below the top part. Instead of allowing only two types of block matrices, one for the horizontal line and one for the diagonal, we generalize the n-fold setting to allow for arbitrary matrices in every block. We show that such an integer program can be solved in time n^2t^2 phi x (r s delta)^{O(rs^2+ sr^2)} (ignoring logarithmic factors). Here delta is an upper bound on the largest absolute value of an entry of A and phi is the largest binary encoding length of a coefficient of c. This improves upon the previously best algorithm of Hemmecke, Onn and Romanchuk that runs in time n^3t^3 phi x delta^{O(st(r+t))}. In particular, our algorithm is not exponential in the number t of columns of A and B. Our algorithm is based on a new upper bound on the l_1-norm of an element of the Graver basis of an integer matrix and on a proximity bound between the LP and IP optimal solutions tailored for IPs with block structure. These new bounds rely on the Steinitz Lemma. Furthermore, we extend our techniques to the recently introduced tree-fold IPs, where we again present a more efficient algorithm in a generalized setting.

Diversity maximization is an important geometric optimization problem with many applications in recommender systems, machine learning or search engines among others. A typical diversification problem is as follows: Given a finite metric space $(X,d)$ and a parameter $k \in \mathbb{N}$, find a subset of $k$ elements of $X$ that has maximum diversity. There are many functions that measure diversity. One of the most popular measures, called remote-clique, is the sum of the pairwise distances of the chosen elements. In this paper, we present novel results on three widely used diversity measures: Remote-clique, remote-star and remote-bipartition. Our main result are polynomial time approximation schemes for these three diversification problems under the assumption that the metric space is doubling. This setting has been discussed in the recent literature. The existence of such a PTAS however was left open. Our results also hold in the setting where the distances are raised to a fixed power $q\geq 1$, giving rise to more variants of diversity functions, similar in spirit to the variations of clustering problems depending on the power applied to the distances. Finally, we provide a proof of NP-hardness for remote-clique with squared distances in doubling metric spaces.

We consider integer programming problems in standard form max{cTx : Ax = b, x ≥ 0, x ∊ ℤn} where A ∊ ℤm×n, b ∊ ℤm and c ∊ ℤn. We show that such an integer program can be solved in time (m·Δ)O(m) · ||b||∞2, where Δ is an upper bound on each absolute value of an entry in A. This improves upon the longstanding best bound of Papadimitriou (1981) of (m · Δ)O(m2), where in addition, the absolute values of the entries of b also need to be bounded by Δ. Our result relies on a lemma of Steinitz that states that a set of vectors in ℝm that is contained in the unit ball of a norm and that sum up to zero can be ordered such that all partial sums are of norm bounded by m. We also use the Steinitz lemma to show that the ℓ1-distance of an optimal integer and fractional solution, also under the presence of upper bounds on the variables, is bounded by m · (2m · Δ + 1)m. Here Δ is again an upper bound on the absolute values of the entries of A. The novel strength of our bound is that it is independent of n. We provide evidence for the significance of our bound by applying it to general knapsack problems where we obtain structural and algorithmic results that improve upon the recent literature.

We provide simple and fast polynomial-time approximation schemes (PTASs) for several variants of the max-sum diversification problem which, in its most basic form, is as follows: given n points p1,…,pn ∊ ℝq and an integer k, select k points such that the average Euclidean distance between these points is maximized. This problem is commonly applied in web search and information retrieval in order to select a diverse set of representative points from the input. In this context, it has recently received a lot of attention. We present new techniques to analyze natural local- search algorithms. This leads to a for distances of negative type, even subject to a general matroid constraint of rank k, in time O(nk2 log k), when assuming that distance evaluations and calls to the independence oracle are constant time. Negative-type distances include as special cases Euclidean and Manhattan distances, among other natural distances. Our result easily transforms into a PTAS. It improves on the only previously known PTAS for this setting, which relies on convex optimization techniques in an n-dimensional space and is impractical for large data sets. In contrast, our procedure has an (optimal) linear dependence on n. Using generalized exchange properties of matroid intersection, we show that a PTAS can be obtained for matroid- intersection constraints as well. Moreover, our techniques, being based on local search, are conceptually simple and allow for various extensions. In particular, we get asymptotically optimal O(1)-approximations when combining the classic dispersion function with a monotone submodular objective, which is a very common class of functions to measure diversity and relevance. This result leverages recent advances on local-search techniques based on proxy functions to obtain optimal approximations for monotone submodular function maximization subject to a matroid constraint.

We show that the problem of finding the simplex of largest volume in the convex hull of n points in ℚd can be approximated with a factor of O(log d) d/2 in polynomial time. This improves upon the previously best known approximation guarantee of d(d–1)/2 by Khachiyan. On the other hand, we show that there exists a constant c > 1 such that this problem cannot be approximated with a factor of cd, unless P = NP. Our hardness result holds even if n = O(d), in which case there exists a d-approximation algorithm that relies on recent sampling techniques, where is again a constant. We show that similar results hold for the problem of finding the largest absolute value of a subdeterminant of a d × n matrix.

The parametric lattice-point counting problem is as follows: Given an integer matrix A ∊ ℤm×n, compute an explicit formula parameterized by b ∊ ℝm that determines the number of integer points in the polyhedron {x ∊ ℝn: Ax ≤ b}. In the last decade, this counting problem has received considerable attention in the literature. Several variants of Barvinok's algorithm have been shown to solve this problem in polynomial time if the number n of columns of A is fixed. Central to our investigation is the following question: Can one also efficiently determine a parameter b such that the number of integer points in {x ∊ ℝn: Ax ≤ b} is minimized? Here, the parameter b can be chosen from a given polyhedron Q ⊆ ℝm. Our main result is a proof that finding such a minimizing parameter is NP-hard, even in dimension 2 and even if the parametrization reflects a translation of a 2-dimensional convex polygon. This result is established via a relationship of this problem to arithmetic progressions and simultaneous Diophantine approximation. On the positive side we show that in dimension 2 there exists a polynomial time algorithm for each fixed k that either determines a minimizing translation or asserts that any translation contains at most 1 + 1/k times the minimal number of lattice points.

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.

We derive a new upper bound on the diameter of the graph of a polyhedron P = {x ∈ Rn : Ax ≤ b}, where A ∈ Zm×n. The bound is polynomial in n and the largest absolute value of a sub-determinant of A, denoted by Δ. More precisely, we show that the diameter of P is bounded by O(Δ2 n4 log nΔ). If P is bounded, then we show that the diameter of P is at most O(Δ2 n3.5 log nΔ).

We provide the currently fastest randomized (1+epsilon)-approximation algorithm for the closest lattice vector problem in the infinity-norm. The running time of our method depends on the dimension n and the approximation guarantee epsilon by 2(O(n)) (log(1/epsilon))(O(n)) which improves upon the (2+1/epsilon)(O(n)) running time of the previously best algorithm by Blömer and Naewe. Our algorithm is based on a solution of the following geometric covering problem that is of interest of its own: Given epsilon>0, how many ellipsoids are necessary to cover the scaled unit cube [-1+epsilon, 1-epsilon]n such all ellipsoids are contained in the standard unit cube [-1,1]n. We provide an almost optimal bound for the case where the ellipsoids are restricted to be axis-parallel.

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.

We consider the problem of testing whether the maximum additive integrality gap of a family of integer programs in standard form is bounded by a given constant. This can be viewed as a generalization of the integer rounding property, which can be tested in polynomial time if the number of constraints is fixed. It turns out that this generalization is NP-hard even if the number of constraints is fixed. However, if, in addition, the objective is the all-one vector, then one can test in polynomial time whether the additive gap is bounded by a constant.

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.

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 consider an optimization problem arising in the design of controllers for OLED displays. Our objective is to minimize amplitude of the electrical current through the diodes which has a direct impact on the lifetime of such a display. Modeling the problem in mathematical terms yields a class of network flow problems where we group the arcs and pay in each group only for the arc carrying the maximum flow. We develop (fully) combinatorial approximation heuristics suitable for being implemented in the hardware of a control device that drives an OLED display.

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.

Strong and weak simulation relations have been proposed for Markov chains, while strong simulation and strong probabilistic simulation relations have been proposed for probabilistic automata. However, decision algorithms for strong and weak simulation over Markov chains, and for strong simulation over probabilistic automata are not efficient, which makes it as yet unclear whether they can be used as effectively as their non-probabilistic counterparts. This paper presents drastically improved algorithms to decide whether some (discrete- or continuous-time) Markov chain strongly or weakly simulates another, or whether a probabilistic automaton strongly simulates another. The key innovation is the use of parametric maximum flow techniques to amortize computations. We also present a novel algorithm for deciding strong probabilistic simulation preorders on probabilistic automata, which has polynomial complexity via a reduction to an LP problem. When extending the algorithms for probabilistic automata to their continuous-time counterpart, we retain the same complexity for both strong and strong probabilistic simulations.

In polyhedral studies of 0/1 polytopes two prominent problems exist. One is the vertex enumeration problem: Given a system of inequalities, enumerate its feasible 0/1 points. Another one is the convex hull problem: Given a set of 0/1 points in dimension d, enumerate the facets of the corresponding polytope. We present two new approaches for both problems. The novelty of our algorithms is the incorporation of binary decision diagrams (BDDs), a datastructure which has become very popular and effective in hardware verification and computational logic. Our computational results show the strength of our methods. We introduce our new tool azove which is currently the fastest software for counting and enumerating 0/1 points in a polytope.

In this paper, we introduce the notion of a constrained Minkowski sumwhich for two (finite) point-sets P,Q⊆ R2 and a set of k inequalities Ax≥ b is defined as the point-set (P ⊕ Q)Ax≥ b= x = p+q | ∈ P, q ∈ Q, , Ax ≥ b. We show that typical subsequenceproblems from computational biology can be solved by computing a setcontaining the vertices of the convex hull of an appropriatelyconstrained Minkowski sum. We provide an algorithm for computing such a setwith running time O(N log N), where N=|P|+|Q| if k is fixed. For the special case (P⊕ Q)x1≥ β, where P and Q consistof points with integer x1-coordinates whose absolute values arebounded by O(N), we even achieve a linear running time O(N). Wethereby obtain a linear running time for many subsequence problemsfrom the literature and improve upon the best known running times forsome of them.The main advantage of the presented approach is that it provides a generalframework within which a broad variety of subsequence problems canbe modeled and solved.This includes objective functions and constraintswhich are even more complexthan the ones considered before.

Virtual private network design is the following NP-hard problem. We are given a communication network represented as a weighted graph with thresholds on the nodes which represent the amount of flow that a node can send to and receive from the network. The task is to reserve capacities at minimum cost and to specify paths between every ordered pair of nodes such that all valid traffic-matrices can be routed along the corresponding paths. Recently, this network design problem has received considerable attention in the literature. It is motivated by the fact that the exact amount of flow which is exchanged between terminals is not known in advance and prediction is often elusive. The main contributions of this paper are as follows: (1) Using Hu's 2-commodity flow theorem, we provide a new and considerably stronger lower bound on the cost of an optimum solution. With this lower bound we reanalyze a simple routing scheme which has been described in the literature many times, and provide an improved upper bound on its approximation ratio. (2) We present a new randomized approximation algorithm. In contrast to earlier approaches from the literature, the resulting solution does not have tree structure. A combination of our new algorithm with the simple routing scheme yields an expected performance ratio of $3.79$ for virtual private network design. This is a considerable improvement of the previously best known $5.55$-approximation result [A. Gupta, A. Kumar, and T. Roughgarden, Simpler and better approximation algorithms for network design, in Proceedings of the ACM Symposium on Theory of Computing, ACM, New York, 2003, pp. 365–372]. (3) Our VPND algorithm uses a Steiner tree approximation algorithm as a subroutine. It is known that an optimum Steiner tree can be computed in polynomial time if the number of terminals is logarithmic. Replacing the approximate Steiner tree computation with an exact one whenever the number of terminals is sufficiently small, we finally reduce the approximation ratio to $3.55$. To the best of our knowledge, this is the first time that a nontrivial result from exact (exponential) algorithms leads to an improved polynomial-time approximation algorithm.

We consider the problem of scheduling a number of periodic tasks T on a real-time architecture composed of a set of identical processors P connected by a common bus. Each processor p \in P has a certain amount of memory \mu (p). In our setting, a task \tau \in¸ T is specified by the period t(\tau), the memory requirement \mu (\tau), the execution time c(\tau), and the deadline d(\tau). We always assume d (\tau) \leqslant t(\tau). Tasks may communicate with each other by sending messages. We denote the set of messages by M, and for each m \in M, src(m) is the source task of m, dst(m) is the target task of m, l(m) is the length of m, and d(m) is the deadline for m. The problem is to find a mapping \prod\limits_{}{} : T \in P representing an assignment of the tasks to the processors that satisfies timing and resource requirements for both tasks and messages. The problem is known to be NP-hard even if tasks do not communicate with each other [9].

Consider the following illumination problem: given a stage represented by a line segment L and a set of lightsources represented by a set of points S in the plane, assign powers to the lightsources such that every point on the stage receives a sufficient amount -- let's say one unit -- of light while minimizing the overall power consumption. By assuming that the amount of light arriving from a fixed lightsource decreases rapidly with the distance from the lightsource, this becomes an interesting optimization problem.We propose to reconsider the classical illumination problems as known from computational geometry literature (e.g. [12]) under this light attenuation model. This paper examines the simple problem introduced above and presents different solutions, based on convex optimization, discretization and linear programming, as well as a purely combinatorial approximation algorithm. Some experimental results are also provided.

In an industry project with a German car manufacturer we are faced with the challenge of placing a maximum number of uniform rigid rectangular boxes in the interior of a car trunk. The problem is of practical importance due to a European industry norm which requires car manufacturers to state the trunk volume according to this measure.No really satisfactory automated solution for this problem has been known in the past. In spite of its NP hardness, combinatorial optimization techniques, which consider only grid-aligned placements, produce solutions which are very close to the one achievable by a human expert in several hours of tedious work. The remaining gap is mostly due to the constraints imposed by the chosen grid.In this paper we present a new approach which combines the grid-based combinatorial method with Simulated Annealing on a continuous model. This allows us to explore arbitrary orientations and placements of boxes, hence closing the gap even further, and - in some cases - even surpass the manual expert solution.The implemented software system allows our industrial partner to incorporate the trunk volume in a very early stage of the car design process without relying on a repeated and cumbersome manual evaluation of the volume.