Source author record

Shmuel Onn

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.OC Discrete Mathematics Data Structures and Algorithms Computational Complexity math.AG

Catalog footprint

Research overview

19works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

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.

preprint2022arXiv

Matching Orderable and Separable Hypergraphs

A perfect matching in a hypergraph is a set of edges that partition the set of vertices. We study the complexity of deciding the existence of a perfect matching in orderable and separable hypergraphs. We show that the class of orderable hypergraphs is strictly contained in the class of separable hypergraphs. Accordingly, we show that for each fixed $k$ , deciding perfect matching for orderable $k$ -hypergraphs is polynomial time doable, but for each fixed $k\geq 3$ , it is NP-complete for separable hypergraphs.

preprint2018arXiv

A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs

The theory of $n$ -fold integer programming has been recently emerging as an important tool in parameterized complexity. The input to an $n$ -fold integer program (IP) consists of parameter $A$ , dimension $n$ , and numerical data of binary encoding length $L$ . It was known for some time that such programs can be solved in polynomial time using $O(n^{g(A)}L)$ arithmetic operations where $g$ is an exponential function of the parameter. In 2013 it was shown that it can be solved in fixed-parameter tractable (FPT) time using $O(f(A)n^3L)$ arithmetic operations for a single-exponential function $f$ . This, and a faster algorithm for a special case of combinatorial $n$ -fold IP, have led to several very recent breakthroughs in the parameterized complexity of scheduling, stringology, and computational social choice. In 2015 it was shown that it can be solved in strongly polynomial time using $O(n^{g(A)})$ arithmetic operations. Here we establish a result which subsumes all three of the above results by showing that $n$ -fold IP can be solved in strongly polynomial FPT time using $O(f(A)n^3)$ arithmetic operations. In fact, our results are much more general, briefly outlined as follows. - There is a strongly polynomial algorithm for ILP whenever a so-called Graver-best oracle is realizable for it. - Graver-best oracles for the large classes of multi-stage stochastic and tree-fold ILPs can be realized in FPT time. Together with the previous oracle algorithm, this newly shows two large classes of ILP to be strongly polynomial; in contrast, only few classes of ILP were previously known to be strongly polynomial. - We show that ILP is FPT parameterized by the largest coefficient $\|A\|_\infty$ and the primal or dual treedepth of $A$ , and that this parameterization cannot be relaxed, signifying substantial progress in understanding the parameterized complexity of ILP.

preprint2017arXiv

Parameterized Shifted Combinatorial Optimization

Shifted combinatorial optimization is a new nonlinear optimization framework which is a broad extension of standard combinatorial optimization, involving the choice of several feasible solutions at a time. This framework captures well studied and diverse problems ranging from so-called vulnerability problems to sharing and partitioning problems. In particular, every standard combinatorial optimization problem has its shifted counterpart, which is typically much harder. Already with explicitly given input set the shifted problem may be NP-hard. In this article we initiate a study of the parameterized complexity of this framework. First we show that shifting over an explicitly given set with its cardinality as the parameter may be in XP, FPT or P, depending on the objective function. Second, we study the shifted problem over sets definable in MSO logic (which includes, e.g., the well known MSO partitioning problems). Our main results here are that shifted combinatorial optimization over MSO definable sets is in XP with respect to the MSO formula and the treewidth (or more generally clique-width) of the input graph, and is W[1]-hard even under further severe restrictions.

preprint2016arXiv

Efficient solutions for weight-balanced partitioning problems

We prove polynomial-time solvability of a large class of clustering problems where a weighted set of items has to be partitioned into clusters with respect to some balancing constraints. The data points are weighted with respect to different features and the clusters adhere to given lower and upper bounds on the total weight of their points with respect to each of these features. Further the weight-contribution of a vector to a cluster can depend on the cluster it is assigned to. Our interest in these types of clustering problems is motivated by an application in land consolidation where the ability to perform this kind of balancing is crucial. Our framework maximizes an objective function that is convex in the summed-up utility of the items in each cluster. Despite hardness of convex maximization and many related problems, for fixed dimension and number of clusters, we are able to show that our clustering model is solvable in time polynomial in the number of items if the weight-balancing restrictions are defined using vectors from a fixed, finite domain. We conclude our discussion with a new, efficient model and algorithm for land consolidation.

preprint2015arXiv

Huge Unimodular N-Fold Programs

Optimization over $l\times m\times n$ integer $3$ -way tables with given line-sums is NP-hard already for fixed $l=3$ , but is polynomial time solvable with both $l,m$ fixed. In the {\em huge} version of the problem, the variable dimension $n$ is encoded in {\em binary}, with $t$ {\em layer types}. It was recently shown that the huge problem can be solved in polynomial time for fixed $t$ , and the complexity of the problem for variable $t$ was raised as an open problem. Here we solve this problem and show that the huge table problem can be solved in polynomial time even when the number $t$ of types is {\em variable}. The complexity of the problem over $4$ -way tables with variable $t$ remains open. Our treatment goes through the more general class of {\em huge $n$ -fold integer programming problems}. We show that huge integer programs over $n$ -fold products of totally unimodular matrices can be solved in polynomial time even when the number $t$ of brick types is variable.

preprint2015arXiv

Shifted Matroid Optimization

We show that finding lexicographically minimal $n$ bases in a matroid can be done in polynomial time in the oracle model. This follows from a more general result that the shifted problem over a matroid can be solved in polynomial time as well.

preprint2015arXiv

The Unimodular Intersection Problem

We show that finding minimally intersecting $n$ paths from $s$ to $t$ in a directed graph or $n$ perfect matchings in a bipartite graph can be done in polynomial time. This holds more generally for unimodular set systems.

preprint2014arXiv

Robust Integer Programming

We provide a complexity classification of four variants of robust integer programming when the underlying Graver basis is given. We discuss applications to robust multicommodity flows and multidimensional transportation, and describe an effective parametrization of robust integer programming.

preprint2014arXiv

The Huge Multiway Table Problem

Deciding the existence of an $l\times m\times n$ integer threeway table with given line-sums is NP-complete already for fixed $l=3$ , but is in P with both $l,m$ fixed. Here we consider {\em huge} tables, where the variable dimension $n$ is encoded in {\em binary}. Combining recent results on integer cones and Graver bases, we show that if the number of {\em layer types} is fixed, then the problem is in P, whereas if it is variable, then the problem is in NP intersect coNP. Our treatment goes through the more general class of $n$ -fold integer programming problems.

preprint2013arXiv

On the Complexity of Hilbert Refutations for Partition

Given a set of integers W, the Partition problem determines whether W can be divided into two disjoint subsets with equal sums. We model the Partition problem as a system of polynomial equations, and then investigate the complexity of a Hilbert's Nullstellensatz refutation, or certificate, that a given set of integers is not partitionable. We provide an explicit construction of a minimum-degree certificate, and then demonstrate that the Partition problem is equivalent to the determinant of a carefully constructed matrix called the partition matrix. In particular, we show that the determinant of the partition matrix is a polynomial that factors into an iteration over all possible partitions of W.

preprint2012arXiv

Convex Integer Optimization by Constantly Many Linear Counterparts

In this article we study convex integer maximization problems with composite objective functions of the form $f(Wx)$ , where $f$ is a convex function on $\R^d$ and $W$ is a $d\times n$ matrix with small or binary entries, over finite sets $S\subset \Z^n$ of integer points presented by an oracle or by linear inequalities. Continuing the line of research advanced by Uri Rothblum and his colleagues on edge-directions, we introduce here the notion of {\em edge complexity} of $S$ , and use it to establish polynomial and constant upper bounds on the number of vertices of the projection $\conv(WS)$ and on the number of linear optimization counterparts needed to solve the above convex problem. Two typical consequences are the following. First, for any $d$ , there is a constant $m(d)$ such that the maximum number of vertices of the projection of any matroid $S\subset\{0,1\}^n$ by any binary $d\times n$ matrix $W$ is $m(d)$ regardless of $n$ and $S$ ; and the convex matroid problem reduces to $m(d)$ greedily solvable linear counterparts. In particular, $m(2)=8$ . Second, for any $d,l,m$ , there is a constant $t(d;l,m)$ such that the maximum number of vertices of the projection of any three-index $l\times m\times n$ transportation polytope for any $n$ by any binary $d\times(l\times m\times n)$ matrix $W$ is $t(d;l,m)$ ; and the convex three-index transportation problem reduces to $t(d;l,m)$ linear counterparts solvable in polynomial time.

preprint2011arXiv

N-fold integer programming in cubic time

N-fold integer programming is a fundamental problem with a variety of natural applications in operations research and statistics. Moreover, it is universal and provides a new, variable-dimension, parametrization of all of integer programming. The fastest algorithm for $n$ -fold integer programming predating the present article runs in time $O(n^{g(A)}L)$ with $L$ the binary length of the numerical part of the input and $g(A)$ the so-called Graver complexity of the bimatrix $A$ defining the system. In this article we provide a drastic improvement and establish an algorithm which runs in time $O(n^3 L)$ having cubic dependency on $n$ regardless of the bimatrix $A$ . Our algorithm can be extended to separable convex piecewise affine objectives as well, and also to systems defined by bimatrices with variable entries. Moreover, it can be used to define a hierarchy of approximations for any integer programming problem.

preprint2010arXiv

Intractability of approximate multi-dimensional nonlinear optimization on independence systems

We consider optimization of nonlinear objective functions that balance $d$ linear criteria over $n$ -element independence systems presented by linear-optimization oracles. For $d=1$ , we have previously shown that an $r$ -best approximate solution can be found in polynomial time. Here, using an extended Erdős-Ko-Rado theorem of Frankl, we show that for $d=2$ , finding a $ρn$ -best solution requires exponential time.

preprint2010arXiv

The Quadratic Graver Cone, Quadratic Integer Minimization, and Extensions

We consider the nonlinear integer programming problem of minimizing a quadratic function over the integer points in variable dimension satisfying a system of linear inequalities. We show that when the Graver basis of the matrix defining the system is given, and the quadratic function lies in a suitable {\em dual Graver cone}, the problem can be solved in polynomial time. We discuss the relation between this cone and the cone of positive semidefinite matrices, and show that none contains the other. So we can minimize in polynomial time some non-convex and some (including all separable) convex quadrics. We conclude by extending our results to efficient integer minimization of multivariate polynomial functions of arbitrary degree lying in suitable cones.

preprint2009arXiv

Graphs of Transportation Polytopes

This paper discusses properties of the graphs of 2-way and 3-way transportation polytopes, in particular, their possible numbers of vertices and their diameters. Our main results include a quadratic bound on the diameter of axial 3-way transportation polytopes and a catalogue of non-degenerate transportation polytopes of small sizes. The catalogue disproves five conjectures about these polyhedra stated in the monograph by Yemelichev et al. (1984). It also allowed us to discover some new results. For example, we prove that the number of vertices of an $m\times n$ transportation polytope is a multiple of the greatest common divisor of $m$ and $n$ .

preprint2009arXiv

Multicommodity Flow in Polynomial Time

The multicommodity flow problem is NP-hard already for two commodities over bipartite graphs. Nonetheless, using our recent theory of n-fold integer programming and extensions developed herein, we are able to establish the surprising polynomial time solvability of the problem in two broad situations.

preprint2007arXiv

A polynomial oracle-time algorithm for convex integer minimization

In this paper we consider the solution of certain convex integer minimization problems via greedy augmentation procedures. We show that a greedy augmentation procedure that employs only directions from certain Graver bases needs only polynomially many augmentation steps to solve the given problem. We extend these results to convex $N$ -fold integer minimization problems and to convex 2-stage stochastic integer minimization problems. Finally, we present some applications of convex $N$ -fold integer minimization problems for which our approach provides polynomial time solution algorithms.

preprint1997arXiv

A Polynomial Time Algorithm for Vertex Enumeration and Optimization over Shaped Partition Polytopes

We consider the {\em Shaped Partition Problem} of partitioning $n$ given vectors in real $k$ -space into $p$ parts so as to maximize an arbitrary objective function which is convex on the sum of vectors in each part, subject to arbitrary constraints on the number of elements in each part. In addressing this problem, we study the {\em Shaped Partition Polytope} defined as the convex hull of solutions. The Shaped Partition Problem captures ${\cal N}{\cal P}$ -hard problems such as the Max-Cut problem and the Traveling Salesperson problem, and the Shaped Partition Polytope may have exponentially many vertices and facets, even when $k$ or $p$ are fixed. In contrast, we show that when both $k$ and $p$ are fixed, the number of vertices is polynomial in $n$ , and all vertices can be enumerated and the optimization problem solved in strongly polynomial time. Explicitly, we show that any Shaped Partition Polytope has $O(n^{k{p\choose 2}})$ vertices which can be enumerated in $O(n^{k^2p^3})$ arithmetic operations, and that any Shaped Partition Problem is solvable in $O(n^{kp^2})$ arithmetic operations.

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.

Shmuel Onn

Research overview

Is this your work?

19 publications

An Algorithmic Theory of Integer Programming

Matching Orderable and Separable Hypergraphs

A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs

Parameterized Shifted Combinatorial Optimization

Efficient solutions for weight-balanced partitioning problems

Huge Unimodular N-Fold Programs

Shifted Matroid Optimization

The Unimodular Intersection Problem

Robust Integer Programming

The Huge Multiway Table Problem

On the Complexity of Hilbert Refutations for Partition

Convex Integer Optimization by Constantly Many Linear Counterparts

N-fold integer programming in cubic time

Intractability of approximate multi-dimensional nonlinear optimization on independence systems

The Quadratic Graver Cone, Quadratic Integer Minimization, and Extensions

Graphs of Transportation Polytopes

Multicommodity Flow in Polynomial Time

A polynomial oracle-time algorithm for convex integer minimization

A Polynomial Time Algorithm for Vertex Enumeration and Optimization over Shaped Partition Polytopes

See the researcher in context

Building this map preview