**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Publication# New Results in the Theory of Linear and Integer Programming

Abstract

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.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related MOOCs (32)

Related concepts (70)

Related publications (261)

Linear programming

Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming (also known as mathematical optimization). More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints.

Integer programming

An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective function and the constraints (other than the integer constraints) are linear. Integer programming is NP-complete. In particular, the special case of 0-1 integer linear programming, in which unknowns are binary, and only the restrictions must be satisfied, is one of Karp's 21 NP-complete problems.

Polynomial-time approximation scheme

In computer science (particularly algorithmics), a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems). A PTAS is an algorithm which takes an instance of an optimization problem and a parameter ε > 0 and produces a solution that is within a factor 1 + ε of being optimal (or 1 – ε for maximization problems). For example, for the Euclidean traveling salesman problem, a PTAS would produce a tour with length at most (1 + ε)L, with L being the length of the shortest tour.

Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.

Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.

Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.

Nikolaos Geroliminis, Claudia Bongiovanni, Mor Kaspi

This paper offers a new algorithm to efficiently optimize scheduling decisions for dial-a-ride problems (DARPs), including problem variants considering electric and autonomous vehicles (e-ADARPs). The scheduling heuristic, based on linear programming theor ...

In urban air mobility (UAM) networks, takeoff and landing sites, called vertiports, are likely to experience intermittent closures due to, e.g., adverse weather. To ensure safety, all in-flight urban air vehicles (UAVs) in a UAM network must therefore have ...

2024Gruber et al. (2022) offered a framework how to explain "Physical time within human time", solving the 'two times problem: Here, I am asking whether such a problem exists at all. To question the question, I will appeal to neurobiological, evolutionary, and ...