BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Friedrich Eisenbrand

Friedrich Eisenbrand appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computational GeometryData Structures and AlgorithmsDiscrete Mathematicsmath.OCComputational Complexitymath.COLogic in Computer Sciencemath.NT

Catalog footprint

What is connected

15works
8topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

15 published item(s)

preprint2022arXiv

An Algorithmic Theory of Integer Programming

We study the general integer programming problem where the number of variables $n$ is a variable part of the input. We consider two natural parameters of the constraint matrix $A$: its numeric measure $a$ and its sparsity measure $d$. We show that integer programming can be solved in time $g(a,d)\textrm{poly}(n,L)$, where $g$ is some computable function of the parameters $a$ and $d$, and $L$ is the binary encoding length of the input. In particular, integer programming is fixed-parameter tractable parameterized by $a$ and $d$, and is solvable in polynomial time for every fixed $a$ and $d$. Our results also extend to nonlinear separable convex objective functions. Moreover, for linear objectives, we derive a strongly-polynomial algorithm, that is, with running time $g(a,d)\textrm{poly}(n)$, independent of the rest of the input data. We obtain these results by developing an algorithmic framework based on the idea of iterative augmentation: starting from an initial feasible solution, we show how to quickly find augmenting steps which rapidly converge to an optimum. A central notion in this framework is the Graver basis of the matrix $A$, which constitutes a set of fundamental augmenting steps. The iterative augmentation idea is then enhanced via the use of other techniques such as new and improved bounds on the Graver basis, rapid solution of integer programs with bounded variables, proximity theorems and a new proximity-scaling algorithm, the notion of a reduced objective function, and others. As a consequence of our work, we advance the state of the art of solving block-structured integer programs. In particular, we develop near-linear time algorithms for $n$-fold, tree-fold, and $2$-stage stochastic integer programs. We also discuss some of the many applications of these classes.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Approximate $\mathrm{CVP}_{p}$ in time $2^{0.802 \, n}$

We show that a constant factor approximation of the shortest and closest lattice vector problem w.r.t. any $\ell_p$-norm can be computed in time $2^{(0.802 +ε)\, n}$. This matches the currently fastest constant factor approximation algorithm for the shortest vector problem w.r.t. $\ell_2$. To obtain our result, we combine the latter algorithm w.r.t. $\ell_2$ with geometric insights related to coverings.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Block-Structured Integer and Linear Programming in Strongly Polynomial and Near Linear Time

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 integer programming problems and their generalizations which have received considerable attention in the recent literature. The previously known algorithms for these problems are based on the augmentation framework, a tailored integer programming variant of local search. In this paper we propose a different approach. Our algorithm relies on parametric search and a new proximity bound. We show that block-structured linear programming can be solved efficiently via an adaptation of a parametric search framework by Norton, Plotkin, and Tardos in combination with Megiddo's multidimensional search technique. This also forms a subroutine of our algorithm for the integer programming case by solving a strong relaxation of it. Then we show that, for any given optimal vertex solution of this relaxation, there is an optimal integer solution within $\ell_1$-distance independent of the dimension of the problem. This in turn allows us to find an optimal integer solution efficiently. We apply our techniques to integer and linear programming with $n$-fold structure or bounded dual treedepth, two benchmark problems in this field. We obtain the first algorithms for these cases that are both near-linear in the dimension of the problem and strongly polynomial. Moreover, unlike the augmentation algorithms, our approach is highly parallelizable.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A Note on Non-Degenerate Integer Programs with Small Sub-Determinants

The intention of this note is two-fold. First, we study integer optimization problems in standard form defined by $A \in\mathbb{Z}^{m\times{}n}$ and present an algorithm to solve such problems in polynomial-time provided that both the largest absolute value of an entry in $A$ and $m$ are constant. Then, this is applied to solve integer programs in inequality form in polynomial-time, where the absolute values of all maximal sub-determinants of $A$ lie between $1$ and a constant.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Geometric Random Edge

We show that a variant of the random-edge pivoting rule results in a strongly polynomial time simplex algorithm for linear programs $\max\{c^Tx \colon Ax\leq b\}$, whose constraint matrix $A$ satisfies a geometric property introduced by Brunsch and Röglin: The sine of the angle of a row of $A$ to a hyperplane spanned by $n-1$ other rows of $A$ is at least $δ$. This property is a geometric generalization of $A$ being integral and all sub-determinants of $A$ being bounded by $Δ$ in absolute value (since $δ\geq 1/(Δ^2 n)$). In particular, linear programs defined by totally unimodular matrices are captured in this famework ($δ\geq 1/ n$) for which Dyer and Frieze previously described a strongly polynomial-time randomized algorithm. The number of pivots of the simplex algorithm is polynomial in the dimension and $1/δ$ and independent of the number of constraints of the linear program. Our main result can be viewed as an algorithmic realization of the proof of small diameter for such polytopes by Bonifas et al., using the ideas of Dyer and Frieze.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Local Search for Max-Sum Diversification

We provide simple and fast polynomial time approximation schemes (PTASs) for several variants of the max-sum diversification problem which, in its most basic form, is as follows: Given n points p_1,...,p_n in R^d and an integer k, select k points such that the average Euclidean distance between these points is maximized. This problem commonly appears in information retrieval and web-search in order to select a diverse set of points from the input. In this context, it has recently received a lot of attention. We present new techniques to analyze natural local search algorithms. This leads to a (1-O(1/k))-approximation for distances of negative type, even subject to any matroid constraint of rank k, in time O(n k^2 log k), when assuming that distance evaluations and calls to the independence oracle are constant time. Negative type distances include as special cases Euclidean distances and many further natural distances. Our result easily transforms into a PTAS and improves on the only previously known PTAS for this setting, which relies on convex optimization techniques in an n-dimensional space and is impractical for large data sets. In contrast, our procedure has an (optimal) linear dependence on n. Using generalized exchange properties of matroid intersection, we show that a PTAS can be obtained for matroid intersection constraints as well. Moreover, our techniques, being based on local search, are conceptually simple and allow for various extensions. In particular, we get asymptotically optimal O(1)-approximations when combining the classic dispersion function with a monotone submodular objective, which is a very common class of functions to measure diversity and relevance. This result leverages recent advances on local search techniques based on proxy functions to obtain optimal approximations for monotone submodular function maximization subject to a matroid constraint.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Max-sum diversity via convex programming

Diversity maximization is an important concept in information retrieval, computational geometry and operations research. Usually, it is a variant of the following problem: Given a ground set, constraints, and a function $f(\cdot)$ that measures diversity of a subset, the task is to select a feasible subset $S$ such that $f(S)$ is maximized. The \emph{sum-dispersion} function $f(S) = \sum_{x,y \in S} d(x,y)$, which is the sum of the pairwise distances in $S$, is in this context a prominent diversification measure. The corresponding diversity maximization is the \emph{max-sum} or \emph{sum-sum diversification}. Many recent results deal with the design of constant-factor approximation algorithms of diversification problems involving sum-dispersion function under a matroid constraint. In this paper, we present a PTAS for the max-sum diversification problem under a matroid constraint for distances $d(\cdot,\cdot)$ of \emph{negative type}. Distances of negative type are, for example, metric distances stemming from the $\ell_2$ and $\ell_1$ norm, as well as the cosine or spherical, or Jaccard distance which are popular similarity metrics in web and image search.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Node-balancing by edge-increments

Suppose you are given a graph $G=(V,E)$ with a weight assignment $w:V\rightarrow\mathbb{Z}$ and that your objective is to modify $w$ using legal steps such that all vertices will have the same weight, where in each legal step you are allowed to choose an edge and increment the weights of its end points by $1$. In this paper we study several variants of this problem for graphs and hypergraphs. On the combinatorial side we show connections with fundamental results from matching theory such as Hall's Theorem and Tutte's Theorem. On the algorithmic side we study the computational complexity of associated decision problems. Our main results are a characterization of the graphs for which any initial assignment can be balanced by edge-increments and a strongly polynomial-time algorithm that computes a balancing sequence of increments if one exists.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On largest volume simplices and sub-determinants

We show that the problem of finding the simplex of largest volume in the convex hull of $n$ points in $\mathbb{Q}^d$ can be approximated with a factor of $O(\log d)^{d/2}$ in polynomial time. This improves upon the previously best known approximation guarantee of $d^{(d-1)/2}$ by Khachiyan. On the other hand, we show that there exists a constant $c>1$ such that this problem cannot be approximated with a factor of $c^d$, unless $P=NP$. % This improves over the $1.09$ inapproximability that was previously known. Our hardness result holds even if $n = O(d)$, in which case there exists a $\bar c\,^{d}$-approximation algorithm that relies on recent sampling techniques, where $\bar c$ is again a constant. We show that similar results hold for the problem of finding the largest absolute value of a subdeterminant of a $d\times n$ matrix.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On sub-determinants and the diameter of polyhedra

We derive a new upper bound on the diameter of a polyhedron P = {x \in R^n : Ax <= b}, where A \in Z^{m\timesn}. The bound is polynomial in n and the largest absolute value of a sub-determinant of A, denoted by Δ. More precisely, we show that the diameter of P is bounded by O(Δ^2 n^4 log nΔ). If P is bounded, then we show that the diameter of P is at most O(Δ^2 n^3.5 log nΔ). For the special case in which A is a totally unimodular matrix, the bounds are O(n^4 log n) and O(n^3.5 log n) respectively. This improves over the previous best bound of O(m^16 n^3 (log mn)^3) due to Dyer and Frieze.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Bin Packing via Discrepancy of Permutations

A well studied special case of bin packing is the 3-partition problem, where n items of size > 1/4 have to be packed in a minimum number of bins of capacity one. The famous Karmarkar-Karp algorithm transforms a fractional solution of a suitable LP relaxation for this problem into an integral solution that requires at most O(log n) additional bins. The three-permutations-problem of Beck is the following. Given any 3 permutations on n symbols, color the symbols red and blue, such that in any interval of any of those permutations, the number of red and blue symbols is roughly the same. The necessary difference is called the discrepancy. We establish a surprising connection between bin packing and Beck's problem: The additive integrality gap of the 3-partition linear programming relaxation can be bounded by the discrepancy of 3 permutations. Reversely, making use of a recent example of 3 permutations, for which a discrepancy of Omega(log n) is necessary, we prove the following: The O(log^2 n) upper bound on the additive gap for bin packing with arbitrary item sizes cannot be improved by any technique that is based on rounding up items. This lower bound holds for a large class of algorithms including the Karmarkar-Karp procedure.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Minimizing the number of lattice points in a translated polygon

The parametric lattice-point counting problem is as follows: Given an integer matrix $A \in Z^{m \times n}$, compute an explicit formula parameterized by $b \in R^m$ that determines the number of integer points in the polyhedron $\{x \in R^n : Ax \leq b\}$. In the last decade, this counting problem has received considerable attention in the literature. Several variants of Barvinok's algorithm have been shown to solve this problem in polynomial time if the number $n$ of columns of $A$ is fixed. Central to our investigation is the following question: Can one also efficiently determine a parameter $b$ such that the number of integer points in $\{x \in R^n : Ax \leq b\}$ is minimized? Here, the parameter $b$ can be chosen from a given polyhedron $Q \subseteq R^m$. Our main result is a proof that finding such a minimizing parameter is $NP$-hard, even in dimension 2 and even if the parametrization reflects a translation of a 2-dimensional convex polygon. This result is established via a relationship of this problem to arithmetic progressions and simultaneous Diophantine approximation. On the positive side we show that in dimension 2 there exists a polynomial time algorithm for each fixed $k$ that either determines a minimizing translation or asserts that any translation contains at most $1 + 1/k$ times the minimal number of lattice points.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Covering Cubes and the Closest Vector Problem

We provide the currently fastest randomized (1+epsilon)-approximation algorithm for the closest vector problem in the infinity norm. The running time of our method depends on the dimension n and the approximation guarantee epsilon by 2^O(n) (log 1/epsilon)^O(n)$ which improves upon the (2+1/epsilon)^O(n) running time of the previously best algorithm by Blömer and Naewe. Our algorithm is based on a solution of the following geometric covering problem that is of interest of its own: Given epsilon in (0,1), how many ellipsoids are necessary to cover the cube [-1+epsilon, 1-epsilon]^n such that all ellipsoids are contained in the standard unit cube [-1,1]^n? We provide an almost optimal bound for the case where the ellipsoids are restricted to be axis-parallel. We then apply our covering scheme to a variation of this covering problem where one wants to cover [-1+epsilon,1-epsilon]^n with parallelepipeds that, if scaled by two, are still contained in the unit cube. Thereby, we obtain a method to boost any 2-approximation algorithm for closest-vector in the infinity norm to a (1+epsilon)-approximation algorithm that has the desired running time.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Set Covering with Ordered Replacement -- Additive and Multiplicative Gaps

We consider set covering problems where the underlying set system satisfies a particular replacement property w.r.t. a given partial order on the elements: Whenever a set is in the set system then a set stemming from it via the replacement of an element by a smaller element is also in the set system. Many variants of BIN PACKING that have appeared in the literature are such set covering problems with ordered replacement. We provide a rigorous account on the additive and multiplicative integrality gap and approximability of set covering with replacement. In particular we provide a polylogarithmic upper bound on the additive integrality gap that also yields a polynomial time additive approximation algorithm if the linear programming relaxation can be efficiently solved. We furthermore present an extensive list of covering problems that fall into our framework and consequently have polylogarithmic additive gaps as well.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

Flow Faster: Efficient Decision Algorithms for Probabilistic Simulations

Strong and weak simulation relations have been proposed for Markov chains, while strong simulation and strong probabilistic simulation relations have been proposed for probabilistic automata. However, decision algorithms for strong and weak simulation over Markov chains, and for strong simulation over probabilistic automata are not efficient, which makes it as yet unclear whether they can be used as effectively as their non-probabilistic counterparts. This paper presents drastically improved algorithms to decide whether some (discrete- or continuous-time) Markov chain strongly or weakly simulates another, or whether a probabilistic automaton strongly simulates another. The key innovation is the use of parametric maximum flow techniques to amortize computations. We also present a novel algorithm for deciding strong probabilistic simulation preorders on probabilistic automata, which has polynomial complexity via a reduction to an LP problem. When extending the algorithms for probabilistic automata to their continuous-time counterpart, we retain the same complexity for both strong and strong probabilistic simulations.

0 citations0 reviewsNo code linkedOpen access