Search · four archives
Search · four archives
10 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…
Daniel Dadush, Friedrich Eisenbrand, Thomas Rothvoss
Approximate integer programming is the following: For a given convex body $K \subseteq{\mathbb{R}}^n$, either determine whether $K \cap{\mathbb{Z}}^n$ is empty, or find an integer point in the convex body $2\cdot K - c +c$ which is K, scaled by 2 from its center of gravity c. Approximate integer programming can be…
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…
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 +…
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…
Ahmad Abdi, Gérard Cornuéjols, Bertrand Guenin, Levent Tunçel
A rational number is dyadic if it has a finite binary representation $p/2^k$, where p is an integer and k is a nonnegative integer. Dyadic rationals are important for numerical computations because they have an exact representation in floating-point arithmetic on a computer. A vector is dyadic if all its entries are…
Kim-Manuel Klein
We consider so called 2-stage stochastic integer programs (IPs) and their generalized form, so called multi-stage stochastic IPs. A 2-stage stochastic IP is an integer program of the form $\max{c^T x \mid{\mathcal{A}}x = b, \,l \le x \le u,\, x \in{\mathbb{Z}}^{s + nt}}$ where the constraint matrix…
Peiping Shen, Tongli Zhang, Chunfeng Wang
This article presents a new approximation algorithm for globally solving a class of generalized fractional programming problems (P) whose objective functions are defined as an appropriate composition of ratios of affine functions. To solve this problem, the algorithm solves an equivalent optimization problem (Q) via an…