New Results in the Theory of Linear and Integer Programming

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.

Node-weighted network design and maximum sub-determinants

Carsten Moldenhauer

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

ocp

grows from

O(n/\log n)

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)

EPFL2014

Approximation Algorithms for Modern Multi-Processor Scheduling Problems

Martin Niemeier

This thesis is devoted to the design and analysis of algorithms for scheduling problems. These problems are ubiquitous in the modern world. Examples include the optimization of local transportation, managing access to concurrent resources like runways at airports and efficient execution of computing tasks on server systems. Problem instances that appear in the real world often are so large and complex that it is not possible to solve them “by hand”. This rises the need for strong algorithmic approaches, which motivates our focus of study. In this work we consider two types of scheduling problems which gained in importance due to recent technological advances. The first problem comes from the avionics industry and deals with scheduling periodically recurring tasks in a parallel computer network on a plane: Each task comes with a period p and execution time c, and needs to use a processor exclusively for c time units every p time units. The scheduling problem is to assign starting offsets for the first execution of the tasks so that no collision occurs. The second problem is a scheduling problem that arises in highly parallelized processing environments with a shared common resource, e.g., modern multi-core computer architectures. In addition to classical makespan minimization problems such as scheduling on identical machines, each job has an additional resource constraint. The scheduler must ensure that at no time, the accumulated requirement of all active jobs at that time exceeds a given limit. For both types of problems we study their algorithmic complexity in a mathematical, rigorous way by designing approximation algorithms and establishing inapproximability results. We thereby give a characterization of the approximation landscape of these problems. We also consider a more practical perspective: For an engineer from the industry, a rigorous proof that an algorithm finds a solution of certain guaranteed quality for all possible kinds of problem instances is usually not that relevant. It is rather of interest to find “good enough” or even optimal solutions for particular instances that actually appear in the real world in “reasonable” time. We show that structural insights gained in the more theoretical process of designing approximation algorithms can be highly beneficial also for obtaining practical results. In particular, we develop integer programming formulations for the avionics problem based on structural properties revealed in the design of approximation algorithms. These formulations lead to strong tools that, for the first time, enable to algorithmically solve real-world instances from our industrial partner.

EPFL2012

New Algorithmic Paradigms for Discrete Problems using Dynamical Systems and Polynomials

Damian Mateusz Straszak

Optimization is a fundamental tool in modern science. Numerous important tasks in biology, economy, physics and computer science can be cast as optimization problems. Consider the example of machine learning: recent advances have shown that even the most sophisticated tasks involving decision making, can be reduced to solving certain optimization problems. These advances however, bring several new challenges to the field of algorithm design. The first of them is related to the ever-growing size of instances, these optimization problems need to be solved for. In practice, this forces the algorithms for these problems to run in time linear or nearly linear in their input size. The second challenge is related to the emergence of new, harder and harder problems which need to be dealt with. These problems are in most cases considered computationally intractable because of complexity barriers such as NP completeness, or because of non-convexity. Therefore, efficiently computable relaxations for these problems are typically desired. The material of this thesis is divided into two parts. In the first part we attempt to address the first challenge. The recent tremendous progress in developing fast algorithm for such fundamental problems as maximum flow or linear programming, demonstrate the power of continuous techniques and tools such as electrical flows, fast Laplacian solvers and interior point methods. In this thesis we study new algorithms of this type based on continuous dynamical systems inspired by the study of a slime mold Physarum polycephalum. We perform a rigorous mathematical analysis of these dynamical systems and extract from them new, fast algorithms for problems such as minimum cost flow, linear programming and basis pursuit. In the second part of the thesis we develop new tools to approach the second challenge. Towards this, we study a very general form of discrete optimization problems and its extension to sampling and counting, capturing a host of important problems such as counting matchings in graphs, computing permanents of matrices or sampling from constrained determinantal point processes. We present a very general framework, based on polynomials, for dealing with these problems computationally. It is based, roughly, on encoding the problem structure in a multivariate polynomial and then recovering the solution by means of certain continuous relaxations. This leads to several questions on how to reason about such relaxations and how to compute them. We resolve them by relating certain analytic properties of the arising polynomials, such as the location of their roots or convexity, to the combinatorial structure of the underlying problem. We believe that the ideas and mathematical techniques developed in this thesis are only a beginning and they will inspire more work on the use of dynamical systems and polynomials in the design of fast algorithms.

EPFL2018