Multicommodity Flow in Polynomial Time (2009)
Hemmecke, Raymond, Onn, Shmuel, Weismantel, Robert
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...
Shmuel Onn Setup for Nonlinear Discrete Optimization (2009)
Shmuel Onn, De Loera, Shmuel Onn
The problem is: The data is a triple: min/max { f(Wx) : x in S}
Shmuel Onn Some Applications and Examples Where Our Theory Provides (2009)
The set of feasible points is a subset S of Z n suitably presented, e.g.-by asystem of inequalities (often linear inequalities, giving “integer programming”)-by asuitable oracle (membership,...
H.: Nonlinear matroid optimization and experimental design (2009)
Yael Berstein, Jon Lee, Hugo Maruri-aguilar, Shmuel Onn, Eva Riccomagno, Robert Weismantel, ...
Abstract. We study the problem of optimizing nonlinear objective functions over matroids presented by oracles or explicitly. Such functions can be interpreted as the balancing of multicriteria...
Nash-equilibria and N-fold integer programming (2009)
Hemmecke, Raymond, Onn, Shmuel, Weismantel, Robert
Inspired by a paper of R. W. Rosenthal, we investigate generalized Nash-equilibria of integer programming games. We show that generalized Nash-equilibria always exist and are related to an optimal...
Shmuel Onn Some Applications and Examples Where Our Theory Provides (2009)
The set of feasible points is a subset S of Z n suitably presented, e.g.-by asystem of inequalities (often linear inequalities, giving “integer programming”)-by asuitable oracle (membership,...
© Birkhäuser Verlag, Basel, 2001 The (2008)
Radon-split and the Helly-core of a point configuration
ALL LINEAR AND INTEGER PROGRAMS ARE SLIM 3-WAY TRANSPORTATION PROGRAMS ∗ (2008)
Abstract. We show that any rational convex polytope is polynomial-time representable as a 3-way line-sum transportation polytope of “slim ” (r, c, 3) format. This universality theorem has...
Minimal average degree aberration and the state polytope for experimental designs (2008)
Berstein, Yael, Maruri-Aguilar, Hugo, Onn, Shmuel, Riccomagno, Eva, Wynn, Henry
For a particular experimental design, there is interest in finding which polynomial models can be identified in the usual regression set up. The algebraic methods based on Groebner bases provide a...
Framework for Nonlinear Discrete Optimization (2008)
Shmuel Onn, Shmuel Onn, Shmuel Onn
The set of feasible points is a subset S of Z n suitably presented, e.g.-by asystem of inequalities
Nonlinear optimization for matroid intersection and extensions (2008)
Berstein, Yael, Lee, Jon, Onn, Shmuel, Weismantel, Robert
We address optimization of nonlinear functions of the form $f(Wx)$, where $f:\R^d\to \R$ is a nonlinear function, $W$ is a $d\times n$ matrix, and feasible $x$ are in some large finite set $F$ of...
Nonlinear Optimization over a Weighted Independence System (2008)
Lee, Jon, Onn, Shmuel, Weismantel, Robert
We consider the problem of optimizing a nonlinear objective function over a weighted independence system presented by a linear-optimization oracle. We provide a polynomial-time algorithm that...
The Graver complexity of integer programming (2008)
In this article we establish an exponential lower bound on the Graver complexity of integer programs. This provides new type of evidence supporting the presumable intractability of integer...
Geometry © 2004 Springer Science+Business Media, Inc. Convex Combinatorial Optimization ∗ (2008)
Abstract. We introduce the convex combinatorial optimization problem, a far-reaching generalization of the standard linear combinatorial optimization problem. We show that it is strongly polynomial...
The convex dimension of a graph (2008)
Nir Halman, Shmuel Onn, Uriel G. Rothblum
The convex dimension of a graph G = (V, E) is the smallest dimension d for which G admits an injective map f: V − → R d of its vertices into d-space, such that the barycenters of the images of...
The complexity of three-way statistical tables (2008)
Dedicated to Bernd Sturmfels on the occasion of his 40th birthday Abstract. Multiway tables with specified marginals arise in a variety of applications in statistics and operations research. We...
Determination of Social Laws for (2008)
Multi-agent Mobilization, Shmuel Onn, Moshe Tennenholtz Y
In previous work on arti cial social systems, social laws for multi-agent mobilization were hand-crafted for particular network structures. In this work, we introduce an algorithm for the automatic...
Printed in U.S.A. THE VECTOR PARTITION PROBLEM FOR CONVEX OBJECTIVE FUNCTIONS (2008)
Shmuel Onn, Leonard J. Schulman
The partition problem concerns the partitioning of a given set of n vectors in d-space into p parts to maximize an objective function that is convex on the sum of vectors in each part. The problem...
H.: Nonlinear matroid optimization and experimental design (2008)
Yael Berstein, Jon Lee (rip, Hugo Maruri-aguilar, Robert Weismantel (rip, Henry Wynn, ...
Starting in 2007, the MFO publishes a preprint series which mainly contains research results related to a longer stay in Oberwolfach. In particular, this concerns the Research in Pairs-Programme...
Social Network Coordination and Graph Routing (2008)
We consider the problem of coordinating robots moving on a network. Each robot is autonomous and needs to visit various sites of the network at various times. The sequence of destinations for each...
Two graph isomorphism polytopes (2008)
The convex hull $\psi_{n,n}$ of certain $(n!)^2$ tensors was considered recently in connection with graph isomorphism. We consider the convex hull $\psi_n$ of the $n!$ diagonals among these tensors....
S.: Nonlinear Bipartite Matching (2008)
www.elsevier.com/locate/disopt We study the problem of optimizing nonlinear objective functions over bipartite matchings. While the problem is generally intractable, we provide several efficient...
Nonlinear Optimization over a Weighted Independence System (2008)
Jon Lee, Shmuel Onn, Robert Weismantel, Oberwolfach Preprints (owp
Starting in 2007, the MFO publishes a preprint series which mainly contains research results related to a longer stay in Oberwolfach. In particular, this concerns the Research in Pairs-Programme...
Vertex Characterization of Partition Polytopes of Planar Point Sets (2007)
Sharon Aviran, Nissan Lev-Tov, Shmuel Onn, Uriel G. Rothblum
The partition problem concerns the partitioning of n given vectors in d-space into p parts, so as to maximize an objective function which is convex on the sum of vectors in each part. The problem has...
Strongly Signable and Partitionable Posets (2007)
The class of Strongly Signable partially ordered sets is introduced and studied. It is shown that strong signability, reminiscent of Bjorner-Wachs' recursive coatom orderability, provides a...
Colourful Linear Programming and its Relatives (2007)
We consider the following Colourful generalization of Linear Programming: given sets of points S 1 ; \Delta \Delta \Delta ; S k ae IR d , referred to as colours, and a point b 2 IR d , decide whether...
A Colorful Determinantal Identity, a Conjecture of Rota, and Latin Squares (2007)
nnegative. In this note we establish an identity, the Colorful Determinantal Identity, which links the two conjectures. It shows that for any n, the Latin Square Conjecture implies Rota's...
A polynomial oracle-time algorithm for convex integer minimization (2007)
Hemmecke, Raymond, Onn, Shmuel, Weismantel, Robert
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...
Graphs of Transportation Polytopes (2007)
De Loera, Jesús A., Kim, Edward D., Onn, Shmuel, Santos, Francisco
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...
The Graver Complexity of Integer Programming (2007)
In this article we establish an exponential lower bound on the Graver complexity of integer programs. This provides new type of evidence supporting the presumable intractability of integer...
Nonlinear Matroid Optimization and Experimental Design (2007)
Berstein, Yael, Lee, Jon, Maruri-Aguilar, Hugo, Onn, Shmuel, Riccomagno, Eva, Weismantel, Robert, ...
We study the problem of optimizing nonlinear objective functions over matroids presented by oracles or explicitly. Such functions can be interpreted as the balancing of multi-criteria optimization....
Convex Discrete Optimization (2007)
We develop an algorithmic theory of convex optimization over discrete sets. Using a combination of algebraic and geometric tools we are able to provide polynomial time algorithms for solving broad...
The use of edge-directions and linear programming to enumerate vertices (2007)
Abstract Given a list of vectors that contains directions of the edges of a given polytope P and the availability of an algorithm that solves linear programs over P, we describe a method for...
Convex Discrete Optimization (2007)
We develop an algorithmic theory of convex optimization over discrete sets. Using a combination of algebraic and geometric tools we are able to provide polynomial time algorithms for solving broad...
Nonlinear Matroid Optimization and Experimental Design (2007)
Yael Berstein, Jon Lee, Hugo Maruri-aguilar, Shmuel Onn, Eva Riccomagno, Robert Weismantel, ...
We study the problem of optimizing nonlinear objective functions over matroids presented by oracles or explicitly. Such functions can be interpreted as the balancing of multi-criteria optimization....
ACCURACY CERTIFICATES FOR COMPUTATIONAL PROBLEMS WITH CONVEX STRUCTURE by (2007)
Arkadi Nemirovski, Shmuel Onn, Uriel G. Rothblum
The goal of the current paper is to introduce the notion of certificates which verify the accuracy of solutions of computational problems with convex structure; such problems include minimizing...
Jesus De Loera, Jon Lee, Susan Margulies, Shmuel Onn
Systems of polynomial equations over the complex or real numbers can be used to model combinatorial problems. In this way, a combinatorial problem is feasible (e.g. a graph is 3-colorable,...
Nonlinear Bipartite Matching (2006)
We study the problem of optimizing nonlinear objective functions over bipartite matchings. While the problem is generally intractable, we provide several efficient algorithms for it, including a...
N-Fold Integer Programming (2006)
De Loera, Jesús A., Hemmecke, Raymond, Onn, Shmuel, Weismantel, Robert
In this article we study a broad class of integer programming problems in variable dimension. We show that these so-termed {\em n-fold integer programming problems} are polynomial time solvable. Our...
Nowhere-Zero Flow Polynomials (2003)
In this article we introduce the flow polynomial of a digraph and use it to study nowhere-zero flows from a commutative algebraic perspective. Using Hilbert's Nullstellensatz, we establish a relation...
Convex Combinatorial Optimization (2003)
Onn, Shmuel, Rothblum, Uriel G.
We introduce the convex combinatorial optimization problem, a far reaching generalization of the standard linear combinatorial optimization problem. We show that it is strongly polynomial time...
Edge-Directions of Standard Polyhedra with Applications to Network Flows (2003)
Shmuel Onn, Uriel G. Rothblum, Yoav Tangir
Abstract. Recent results show that edge-directions of polyhedra play an important role in (combinatorial) optimization; in particular, a d-dimensional polyhedron with |D | distinct edge-directions...
The Complexity of Three-Way Statistical Tables (2002)
Multi-way tables with specified marginals arise in a variety of applications in statistics and operations research. We provide a comprehensive complexity classification of three fundamental...
The Hilbert Zonotope and a Polynomial Time Algorithm for Universal Grobner Bases (2002)
Babson, Eric, Onn, Shmuel, Thomas, Rekha
We provide a polynomial time algorithm for computing the universal Gr\"obner basis of any polynomial ideal having a finite set of common zeros in fixed number of variables. One ingredient of our...
Convex Matroid Optimization (2002)
We consider a problem of optimizing convex functionals over matroid bases. It is richly expressive and captures certain quadratic assignment and clustering problems. While generally NP-hard, we show...
Abstract. One of the classical problems concerning the peg solitaire game is the feasibility issue. Tools used to show the infeasibility of various peg games include valid inequalities, known as...
Automated transformations for PDE systems with applications to multigrid solvers (with (2002)
Yossi Gil, Zvika Gutterman, Shmuel Onn, Irad Yavneh
Abstract. An approach for transformingsystems of partial differential equations in order to obtain new formulations which are more accessible to numerical solution is studied. An algorithm is...
Social Network Coordination and Graph Routing (2002)
We consider the problem of coordinating robots moving on a network. Each robot is autonomous and needs to visit various sites of the network at various times. The sequence of destinations for each...
Automated Transformations for PDE Systems with Application to Multigrid Solvers (2001)
Yossi Gil, Zvika Gutterman, Shmuel Onn, Irad Yavneh, Irad Yavneh
An approach for transforming systems of partial differential equations in order to obtain new formulations which are more accessible to numerical solution is studied. An algorithm is developed for...
David Avis, Antoine Deza, Shmuel Onn
Abstract. The classical game of peg solitaire has uncertain origins, but was certainly popular by the time of Louis XIV, and was described by Leibniz in 1710. One of the classical problems concerning...
David Avis, Antoine Deza, Shmuel Onn
Abstract. The classical game of peg solitaire has uncertain origins, but was certainly popular by the time of Louis XIV, and was described by Leibniz in 1710. One of the classical problems concerning...
Linear Shaped Partition Problems (2000)
Frank K. Hwang, Shmuel Onn, Uriel G. Rothblum
We establish the polynomial time solvability of a class of vector partition problems with linear objectives subject to restrictions on the number of elements in each part. 1 Shaped Partition Problems...
AND REVIEW OF MAIN RESULTS (1999)
Frank K. Hwang, Shmuel Onn, Uriel G. Rothblum
Abstract: We consider a class of partitioning problems where the partitioned set is a finite set of real numbers and the objective function of a partition is a function of the vector whose...
CUTTING CORNERS Shmuel Onn (1999)
Bernd Sturmfe Ls, Shmuel Onn, Bernd Sturmfels
this paper is the corner cut polyhedron, which we define as follows: P
CUTTING CORNERS Shmuel Onn (1999)
Bernd Sturmfe Ls, Shmuel Onn, Bernd Sturmfels
this paper is the corner cut polyhedron, which we define as follows: P
An ordered partition of a set of n points in the d dimensional Euclidean space is called a separable partition if the convex hulls of the parts are pairwise disjoint. For each fixed p and d we...
this paper is the corner cut polyhedron, which we define as follows: P
The object of this study in this paper is the corner cut polyhedron, which we define as follows: d 1 n 1 n d d Pn � conv � � �� � � � : �,..., � are n distinct vectors in N 4 �...
An ordered partition of a set of n points in the d dimensional Euclidean space is called a separable partition if the convex hulls of the parts are pairwise disjoint. For each fixed p and d we...
One of the classical problems concerning the peg solitaire game is the feasibility issue. Tools used to show the infeasibility of various peg games include valid inequalities, known as...
Hwang, Frank K., Onn, Shmuel, Rothblum, Uriel G.
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...
Frank K. Hwang, Shmuel Onn, Uriel G. Rothblum, G. Rothblum
. We consider the 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...
Determination of Social Laws for Multi-Agent Mobilization (1997)
Shmuel Onn, Multi-agent Mobilization, Moshe Tennenholtz
In previous work on artificial social systems, social laws for multi-agent mobilization were hand-crafted for particular network structures. In this work, we introduce an algorithm for the automatic...
Determination of Social Laws for Multi-Agent Mobilization (1997)
Shmuel Onn, Multi-agent Mobilization, Moshe Tennenholtz
In previous work on artificial social systems, social laws for multi-agent mobilization were hand-crafted for particular network structures. In this work, we introduce an algorithm for the automatic...
Lattice-Free Polytopes and Their Diameter (1995)
A convex polytope in real Euclidean space is lattice-free if it intersects some lattice in space exactly in its vertex set. Lattice-free polytopes form a large and computationally hard class, and...
A Note On Lattice Simplices And Toric Varieties (1994)
such that den(A \Gamma1 ) = jdet(A)j = n and den(e d \Delta A \Gamma1 ) = 1. Implication. The simplicial cones defined by the matrices in part (b) of this Theorem define a family of affine toric...
Hilbert Series of Group Representations and Gröbner Bases for Generic Modules (1994)
Each matrix representation ß : G \Gamma! GL n (K) of a finite group G over a field K induces an action of G on the module A n over the polynomial algebra A = K[x 1 ; \Delta \Delta \Delta ; x n ]....
Approximating Oracle Machines for Combinatorial Optimization (1994)
. For every k, an oracle Turing machine M k , and rational polytopes P k (S) for all n and S ` f0; 1g n , are constructed; querying from the set S given as an oracle, M S k solves the separation...
A Quantitative Steinitz' Theorem (1994)
. Any 3-dimensional convex polytope with n vertices can be realized in Euclidean 3-space with all coordinates of all vertices being integers of absolute value not exceeding n 169n 3 . 1. Introduction...
A Quantitative Steinitz' Theorem (1994)
. Any 3-dimensional convex polytope with n vertices can be realized in Euclidean 3-space with all coordinates of all vertices being integers of absolute value not exceeding n 169n 3 . 1. Introduction...
Geometry, Complexity, and Combinatorics of Permutation Polytopes (1993)
Each group G of permutation matrices gives rise to a permutation polytope P (G) = conv(G) ae IR d\Thetad , and for any x 2 IR d , an orbit polytope P (G; x) = conv(G \Delta x). A broad subclass is...
Hilbert Series of Group Representations and Gr"obner Bases for Generic Modules (1993)
1 Introduction Each matrix representation ss: G \Gamma! GLn(K) of a finite group G over a field K induces an action of G on the free IN-graded module An over the algebra A = K[x1; \Delta \Delta...
On the Diameter of Convex Polytopes (1992)
Peter Kleinschmidt, Shmuel Onn
(P )gj \Gamma 1, and by F \Gamma (P; w) and F+ (P; w) denote the faces of P containing those vertices attaining the minimum and maximum values under w, respectively. Theorem Let P be a d-polytope in...
Discrete geometry, group representations and combinatorial optimization : an interplay / (1992)
Thesis (Ph.D.)--Cornell University, August, 1992.
On the Geometry and Computational Complexity of Radon Partitions in the Integer Lattice (1991)
. The following integer analogue of a Radon partition in affine space R d is studied: A partition (S; T ) of a set of integer points in R d is an integral Radon partition if the convex hulls of S and...
Graphs of Transportation Polytopes
Jesús A. De, Loera Edward, D. Kim, Shmuel Onn, Francisco Santos
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...
A Polynomial Time Algorithm for Shaped Partition Problems
Frank K. Hwang, Shmuel Onn, Uriel G. Rothblum
We consider the class of Shaped Partition Problems of partitioning n given vectors in d- dimensional criteria space into p parts so as to maximize an arbitrary objective function which is convex on...