Search · four archives
Search · four archives
17 papers · ranked by Valyu relevance
S Hitarth, Alessio Mansutti, Guruprerana Shabadi
This paper presents the first study of the complexity of the optimization problem for integer linear-exponential programs which extend classical integer linear programs with the exponential function x 7→ 2 x and the remainder function (x, y) 7→ (x mod 2 y ). The problem of deciding if such a program has a solution was…
Dmitry Chistikov, Alessio Mansutti, Mikhail R. Starchak
This paper provides an NP procedure that decides whether a linear-exponential system of constraints has an integer solution. Linear-exponential systems extend standard integer linear programs with exponential terms 2 x and remainder terms (x mod 2y ). Our result implies that the existential theory of the structure (N…
Joël Ouaknine, Amaury Pouly, João Sousa-Pinto, James Worrell
We consider a continuous analogue of (Babai et al. 1996)'s and (Cai et al. 2000)'s problem of solving multiplicative matrix equations. Given k + 1 square matrices A1, . . . , Ak, C, all of the same dimension, whose entries are real algebraic, we examine the problem of deciding whether there exist non-negative reals t1…
Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider
'Stefan Schneider'] We give an exact algorithm for the 0-1 Integer Linear Programming problem with a linear number of constraints that improves over exhaustive search by an exponential factor. Specifically, our algorithm runs in time 2(1−poly(1/c))n where n is the number of variables and cn is the number of…
Volker Kaibel, Stefan Weltge
Let X be the set of integer points in some polyhedron. We investigate the smallest number of facets of any polyhedron whose set of integer points is X. This quantity, which we call the relaxation complexity of X, corresponds to the smallest number of linear inequalities of any integer program having X as the set of…
Alfonso Cevallos, Stefan Weltge, Rico Zenklusen
Mixed-integer mathematical programs are among the most commonly used models for a wide set of problems in Operations Research and related fields. However, there is still very little known about what can be expressed by small mixed-integer programs. In particular, prior to this work, it was open whether some classical…
Loïs Paulin, David Cœurjolly, Nicolas Bonneel, Jean‐Claude Iehl + 2 more
'Victor Ostromoukhov' 'Alexander Keller'] Abstract In quasi-Monte Carlo methods, generating high-dimensional low discrepancy sequences by generator matrices is a popular and efficient approach. Historically, constructing or finding such generator matrices has been a hard problem. In particular, it is challenging to…
Friedrich Eisenbrand, Robert Weismantel
We consider integer programming problems in standard form max{c T x : Ax = b, x > 0, x ∈ Z n } where A ∈ Z m×n , b ∈ Z m and c ∈ Z n . We show that such an integer program can be solved in time (m ·∆) O(m) · kbk 2 ∞, where ∆ is an upper bound on each absolute value of an entry in A. This improves upon the longstanding…
Kenya Ueno
In this paper, we show O(1.415n )-time and O(1.190n )-space exact algorithms for 0-1 integer programs where constraints are linear equalities and coefficients are arbitrary real numbers. Our algorithms are quadratically faster than exhaustive search and almost quadratically faster than an algorithm for an inequality…
Qing Ye, Weijun Xie
Exponents and logarithms are fundamental components in many important applications such as logistic regression, maximum likelihood, relative entropy, and so on. Since the exponential cone can be viewed as the epigraph of perspective of the natural exponential function or the hypograph of perspective of the natural…
Daniel Lokshtanov
In the Integer Quadratic Programming problem input is an n × n integer matrix Q, an m × n integer matrix A and an m-dimensional integer vector b. The task is to find a vector x ∈ Z n minimizing x TQx, subject to Ax ≤ b. We give a fixed parameter tractable algorithm for Integer Quadratic Programming parameterized by n +…
Daniel Dadush, A. B. Leonard, Lars Rohwedder, José Verschae
We consider box-constrained integer programs with objective g(W x)+ c Tx, where g is a "complicated" function with an m dimensional domain. Here we assume we have n ≫ m variables and that W ∈ Z m×n is an integer matrix with coefficients of absolute value at most ∆. We design an algorithm for this problem using only the…
Pol Puigdemont, Stratis Skoulakis, Grigorios G. Chrysos, Volkan Cevher
'Volkan Cevher'] Cutting plane methods are a fundamental approach for solving integer linear programs (ILPs). In each iteration of such methods, additional linear constraints (cuts) are introduced to the constraint set with the aim of excluding the previous fractional optimal solution while not affecting the optimal…
Jana Cslovjecsek, Friedrich Eisenbrand, Christoph Hunkenschröder, Lars Rohwedder + 1 more
'Lars Rohwedder' 'Robert Weismantel'] 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…
Chassidy Bozeman, Joshua M. Carlson, Michael Dairyko, Derek S. Young + 1 more
'Michael Young'] A vertex v in a porous exponential dominating set assigns weight 1 2 dist(v,u) to vertex u. A porous exponential dominating set of a graph G is a subset of V (G) such that every vertex in V (G) has been assigned a sum weight of at least 1. In this paper the porous exponential dominating number, denoted…
Jana Cslovjecsek, Friedrich Eisenbrand, Michał Pilipczuk, Moritz Venzin + 1 more
'Moritz Venzin' 'Robert Weismantel'] We consider the problem of solving integer programs of the form min{ c |x : Ax = b, x > 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…
Cornelius Brand, Martin Koutecký, Alexandra Lassota, Sebastian Ordyniak
'Sebastian Ordyniak'] An influential 1990 paper of Hochbaum and Shanthikumar made it common wisdom that "convex separable optimization is not much harder than linear optimization" [JACM 1990]. We exhibit two fundamental classes of mixed integer (linear) programs that run counter this intuition. Namely those whose…