Node-weighted network design and maximum sub-determinants

We consider the Node-weighted Steiner Forest problem on planar graphs. Demaine et al. showed that a generic primal-dual algorithm gives a 6-approximation. We present two different proofs of an approximation factor of~ $3$ . Then, we draw a connection to Goemans and Williamson who apply the primal-dual algorithm to feedback problems on planar graphs. We reduce these problems to Node-weighted Steiner Forest and show that for the graphs in the reductions their respective linear programming relaxations are equivalent to each other. This explains why both type of problems can be approximated with primal-dual methods. We show that the largest sub-determinant of a matrix $A\in Q^{d\times n}$ can be approximated with a factor of $O(\log d)^{d/2}$ in polynomial time. This problem also subsumes the problem of finding a simplex of largest volume in the convex hull of $n$ points in $Q^d$ for which we obtain the same approximation guarantee. The previously best known approximation guarantee for both problems was $d^{(d-1)/2}$ by Khachiyan. We further show that it is NP-hard to approximate both problems with a factor of~ $c^d$ for some explicit constant~ $c$ . We highlight the importance of sub-determinants in combinatorial optimization by showing their significance in two problems. First, the Stable Set problem asks for a maximum cardinality set of pairwise non-adjacent vertices. The problem is NP-hard to approximate with factor $n^{1-\epsilon}$ for any $\epsilon>0$ , where $n$ is the number of vertices. We restrict to instances where the sub-determinants of the constraint matrix are bounded by a function in~ $n$ . This is equivalent to restricting to graphs with bounded odd cycle packing number $ocp$ , the maximum number of vertex-disjoint odd cycles in the graph. We obtain a polynomial-time approximation scheme for graphs with $ocp=o(n/\log n)$ . Further, we obtain an $\alpha$ -approximation algorithm for general graphs where~ $\alpha$ smoothly increases from a constant to $n$ as $ocp$ grows from $O(n/\log n)$ to $n/3$ . In contrast, we show that assuming the exponential-time hypothesis, Stable Set cannot be solved in polynomial time if $ocp=\Omega(\log^{1+\epsilon} n)$ for some $\epsilon>0$ . Second, we consider coloring $n$ intervals with $k$ colors such that at each point on the line, the maximal difference between the number of intervals of any two colors is at most one. This problem induces a totally unimodular constraint matrix and is therefore efficiently solvable. We construct a fast algorithm with running time $O(n \log n + kn\log k)$ .

New Results in the Theory of Linear and Integer Programming

Nicolai Hähnle

The polynomial Hirsch conjecture states that the vertex-edge diameter of a d-dimensional polyhedron with n facets is bounded by a polynomial in d and n. For the special case where the polyhedron is defined as the set of points satisfying a system Ax ≤ b of linear inequalities where A is an integer matrix with subdeterminants bounded by ∆, we prove an upper bound of O(∆2d4 logd∆) on the diameter. This special case includes the case of totally unimodular matrices, which are common in fundamental problems of combinatorial optimization such as network flows. Our bound can be improved slightly when the polyhedron is known to be bounded. We obtain this result by assigning a volume to every vertex of the polyhedron via its normal fan and proving a volume expansion property using isoperimetric inequalities. We show a (1 + ε)-approximation algorithm for the closest lattice vector problem in the l∞- norm with a running time bounded by (2log(1/ε))O(d) ·bO(1), where d is the dimension and b thebinaryencodinglengthoftheprobleminstance. Thisimprovesuponthe(2+1/ε)O(d)·bO(1) running time of the previously fastest known algorithm. Our approach is based on a geometric covering problem: find a family of parallelepipeds that cover the cube [−1 + ε, 1 − ε]d , while at the same time every parallelepiped remains within the cube [−1, 1]d even when scaled around its centroid by a factor of 2. We then reduce the original problem to the problem of solving an approximate integer program for each of the parallelepipeds, which can be done using existing approximation algorithms for the closest vector problem. We also discuss some variants of the geometric covering problem. We investigate two questions related to parameterized families of integer programs. First, we relatetheadditiveintegralitygapofafamilyofintegerprogramsmin{cTx : Ax=b,x≥0,x∈ Zn }, where b ∈ Zd is a parameter, to a generalization of the Hilbert basis of a convex cone. We show that under certain conditions, such as when d is fixed and c = 1 is the all ones vector, we can decide in polynomial time whether the additive integrality gap is bounded by a constant γ for all choices of parameter. This is achieved by partitioning the space of parameters using a hyperplane arrangement, and reducing the problem to one integer program for every cell in the arrangement. This decision procedure also yields an alternative method for deciding whether a set of generating vectors of a cone is a Hilbert basis. On the other hand, the general problem of deciding whether the additive integrality gap of such a family of integer programs is bounded is N P -hard even when d is fixed. We show this by a reduction from the coin problem, also known as the Frobenius problem. Second, consider a family of integer programs Ax ≤ b,x ∈ Zd, where b ∈ B is a parameter. Parametric integer programming is the problem of deciding whether all integer programs in vii the family are feasible. We investigate the related problem of finding a parameter b ∈ B that minimizes the number of integer solutions x ∈ Zd of Ax ≤ b. We show that, unlike parametric integer programming, this problem is already N P -hard when d = 2 and B ∼= R. In fact, the following special case is N P -hard: given a convex polygon P and a direction v ∈ Z2 , find t ∈ R that minimizes the number of integer points in P + t v . We show this by a reduction from simultaneous Diophantine approximation. On the positive side, we give a polynomial time approximation scheme for this particular problem.

EPFL2012

New Graph Algorithms via Polyhedral Techniques

Jakub Tarnawski

In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. Somewhat surprisingly, similar polyhedral techniques can be harnessed in the two seemingly disparate settings. In the first part of the thesis we address a benchmark problem in combinatorial optimization: the asymmetric traveling salesman problem (ATSP). It consists in finding the shortest tour that visits all vertices of a given directed graph with weights on edges. Due to its NP-hardness, the theoretical study of algorithms for ATSP has focused on approximation algorithms: ones that are provably both efficient and give solutions competitive with the optimum. Specifically, a rho-approximation algorithm for ATSP is one that runs in polynomial time and always outputs a tour that is at most rho times longer than the shortest tour. Finding such an approximation algorithm with rho bounded (i.e., a constant factor) had been a long-standing open problem. In this thesis, we give such an algorithm. Our approximation guarantee is analyzed with respect to the standard linear programming relaxation, and thus our result also confirms the conjectured constant integrality gap of that relaxation. Our techniques build upon the constant-factor approximation algorithm for the special case of node-weighted metrics due to Svensson. In particular, we give a generic reduction to structured instances that resemble but are more general than those arising from node-weighted metrics. This reduction takes advantage of a laminar family of vertex sets that arises from the linear programming relaxation. In the second part of the thesis we address the perfect matching problem. The first polynomial-time algorithm for it, given by Edmonds in 1965, is historically associated with the introduction of the class P and our notion that polynomial-time'' means efficient''. That algorithm is sequential and deterministic. We have also known since the 1980s that the matching problem has efficient parallel algorithms if the use of randomness is allowed. Formally, it is in the class RNC, i.e., it has randomized algorithms that use polynomially many processors and run in polylogarithmic time. However, we do not know if randomness is necessary - that is, whether the matching problem is in the class NC. In this thesis we show that the matching problem is in quasi-NC. That is, we give a deterministic parallel algorithm that runs in O(log^3 n) time on n^{O(log^2 n)} processors. The result is obtained by a derandomization of the Isolation Lemma for perfect matchings, which was introduced in the classic paper by Mulmuley, Vazirani and Vazirani to obtain an RNC algorithm. Our proof extends the framework of Fenner, Gurjar and Thierauf, who proved the analogous result in the special case of bipartite graphs. Compared to that setting, several new ingredients are needed due to the significantly more complex structure of perfect matchings in general graphs. In particular, our proof heavily relies on the laminar structure of the faces of the perfect matching polytope.

EPFL2019

On the computational complexity of periodic scheduling

Thomas Rothvoss

In periodic scheduling jobs arrive regularly and have to be executed on one or several machines or processors. An enormous amount of literature has been published on this topic, e.g. the founding work of Liu & Layland [LL73] is among the top cited computer science papers, according to Citeseer database. The majority of these papers is mainly concerned about practical applications and several important theoretical questions remained unsolved. Let S be a set of periodic tasks, where each task τ ∈ S releases a job of running time c(τ) and relative deadline d(τ) at each integer multiple of its period p(τ). In the single-processor scheduling one considers rules like Earliest-Deadline-First (EDF) or Rate-monotonic (RM) scheduling, that determine the order, in which the jobs have to be processed. The principal question here is to predict, whether such a schedule is feasible, i.e. whether all jobs are finished before their individual deadlines. It was well-known that to validate the feasibility of an EDF-schedule, one has to evaluate the condition But the complexity status of this test remained unknown, despite of many heuristic approaches in the literature. We prove that testing this condition is coNP-hard even in special cases, answering an open question of Baruah & Pruhs [BP09]. For a static-priority schedule of implicit-deadline tasks, i.e. d(τ) = p(τ), it is known that the jobs of a task τ will meet their deadlines if and only if there exists a fix-point r ∈ [0,p(τ)] of the equation where the sum ranges over all tasks with priority higher than τ . We settle the complexity status of this problem by proving its NP-hardness, even if one asks for modest approximations. Both results are achieved by bridging the more practically oriented area of Real-time scheduling and the field of algorithmic number theory. In fact, the intractability follows by a chain of reductions to simultaneous Diophantine approximation (SDA), which is a classical problem in the geometry of numbers and deals with finding a small denominator Q ∈ {1,…,N}, that yields a good approximation to a given vector of rational numbers α ∈ Qn, i.e. maxi=1,…,n |Qαi - ⎡Qαi⎦| ≤ ε. We strengthen existing hardness results for SDA such that they admit intractability results also for a directed version, where the goal is to find a Q ∈ {1,…,N} with maxi=1,…,n(⎡Qαi⎤ - Qαi) ≤ ε. We show that this problem remains NP-hard if one asks for an approximation that may exceed the bound N by a factor of nO(1/loglogn) and the error bound ε by 2nO(1). As an application we are able to answer an open question of Conforti et al. [CSW08] negatively by obtaining NP-hardness for the problem of optimizing a linear function over a mixing set {(s,y ∈ R≥0 × Zn | s + aiyi ≥ bi ∀i = 1,…, n}. Furthermore we obtain that, regardless to the used ‖ · ‖p-norm, the problem of finding a shortest positive vector in a lattice is not approximable within a factor of nO(1/loglogn), unless NP = P. For scheduling constrained-deadline tasks (i.e. d(τ) ≤ p(τ)) with a static-priority policy one possibly needs machines, which are a factor f > 1 faster than it is needed for the EDF policy. Baruah & Burns [BB08] sandwiched this factor between 1.5 and 2. We pinpoint this value to f = 1/Ω ≈ 1.76 by characterizing the properties of task systems, which attain this value. Here, Ω ≈ 0.56 is a well known constant from complex calculus, defined as real root of x · ex = 1. We further consider a multiprocessor setting, where a given set of tasks has to be assigned to machines, such that each partition is RM-schedulable and the number of occupied processors is minimized. For the popular case that the tasks are equipped with implicit-deadlines, i.e. d(τ) = p(τ), we develop new algorithms as well as intractability results: We state an asymptotic PTAS under resource augmentation. This is achieved by two concepts: First we derive that using a merging and clustering procedure, the instance can be modified, such that the utilization of tasks is lowerbounded by a constant, without excluding near-optimal solutions. Secondly, we introduce a relaxed notion of feasibility, which yields a drastic reduction of complexity and admits to compute solutions via dynamic programming. We introduce a simple First-Fit-like heuristic and obtain that this algorithm behaves nearly optimal on average, by proving that the expected waste is upperbounded by O(n3/4(log n)3/8), if the instance of n tasks is generated randomly. Here, we assume that the utilization values c(τ)/p(τ) of the tasks are drawn uniformly at random from [0, 1]. We state a new approximation algorithm with a running time of O(n3), which can be sketched as follows: Create a graph with the tasks being the nodes and insert edges, if both incident tasks can be scheduled together on a processor. Then define suitable vertex costs and compute a min-cost matching, where the costs are the sum of edge costs plus the vertex costs of not covered nodes. From such a matching solution we can then extract a feasible multiprocessor schedule. The approximation ratio of this algorithm can be proven to tend to 3/2, improving over the previously best known ratio of 7/4 [BLOS95]. We consider a column-based linear programming relaxation for this multiprocessor scheduling problem and derive that the asymptotic integrality gap is located between 4/3 ≈ 1.33 and 1 + ln(2) ≈ 1.69. We disprove the existence of an asymptotic FPTAS, which yields that the problem is strictly harder to approximate than its special case of Bin Packing.

EPFL2009