Global Routing in VLSI Design: Algorithms, Theory, and Computational Practice (2008)
Antoine Deza, Chris Dickson, Tamás Terlaky, Anthony Vanelli, Hu Zhang
Global routing in VLSI (very large scale integration) design is one of the most challenging discrete optimization problems in computational theory and practice. In this paper, we present a polynomial...
Line and Plane Arrangements with Large Average Diameter (2008)
Abstract: Let ∆A(n, d) denote the largest possible average diameter of a bounded cell of a simple arrangement defined by n hyperplanes in dimension d. We have ∆A(n, 2) ≤ 2 + 2 n−1 in the...
A counterexample to the dominating set conjecture (2008)
The metric polytope metn is the polyhedron associated with all semimetrics on n nodes and defined by the triangle inequalities xij − xik − xjk ≤ 0 and xij + xik + xjk ≤ 2 for all triples i,...
Title: Colourful Simplicial Depth Authors: (2008)
Antoine Deza, Sui Huang, Tamon Stephen, Tamás Terlaky, Antoine Deza, Sui Huang, ...
Abstract. Inspired by Bárány’s colourful Carathéodory theorem [Bár82], we introduce a colourful generalization of Liu’s simplicial depth [Liu90]. We prove a parity property and conjecture...
THE COLOURFUL FEASIBILITY PROBLEM (2008)
Antoine Deza, Sui Huang, Tamon Stephen, Tamás Terlaky
Abstract. We study a colourful generalization of the linear programming feasibility problem, comparing the algorithms introduced by Bárány and Onn with new methods. This is a challenging problem on...
Geometry © 2006 Springer Science+Business Media, Inc. (2008)
Colourful Simplicial Depth, Antoine Deza, Sui Huang, Tamon Stephen, Tamás Terlaky
Abstract. Inspired by Bárány’s Colourful Carathéodory Theorem [4], we introduce a colourful generalization of Liu’s simplicial depth [13]. We prove a parity property and conjecture that the...
THE COLOURFUL FEASIBILITY PROBLEM (2008)
Antoine Deza, Sui Huang, Tamon Stephen, Tamás Terlaky
Abstract. We study a colourful generalization of the linear programming feasibility problem, comparing the algorithms introduced by Bárány and Onn with new methods. We perform benchmarking on...
DOI 10.1007/s10801-006-6924-6 The isometries of the cut, metric and hypermetric cones (2008)
Antoine Deza, Boris Goldengorin, Dmitrii V. Pasechnik
Abstract We show that the symmetry groups of the cut cone Cutn and the metric cone Metn both consist of the isometries induced by the permutations on {1,...,n}; that is, Is(Cutn) = Is(Metn) �...
Research Contributions Overview Shmuel Onn (2008)
Imre Bárány, Yael Berstein, Jesus De Loera, Antoine Deza, Raymond Hemmecke, Peter Kleinschmidt, ...
My research aims at the development of efficient algebraic and geometric methods for discrete optimization, the investigation of the underlying mathematical structures, and the employment of such...
Skeletons of some relatives of the n-cube (2007)
Antoine Deza, Antoine Deza, Michel Deza, Michel Deza
We study the skeleton of several polytopes related to the n-cube, the halved n-cube, and the folded n-cube. In particular, the Gale polytope of the n-cube, its dual and the duals of the halved n-cube...
Antoine Deza, Komei Fukuda, Dmitrii Pasechnik, Masanori Sato
Abstract. We consider convex polyhedra with applications to wellknown combinatorial optimization problems: the metric polytope mn and its relatives. For n 6 the description of the metric polytope is...
On the Face Lattice of the Metric Polytope (2007)
Antoine Deza Komei, Antoine Deza, Komei Fukuda, Tomohiko Mizutani, Cong Vo
In this paper we study enumeration problems for polytopes arising from combinatorial optimization problems. While these polytopes turn out to be quickly intractable for enumeration algorithms...
On the binary solitaire cone David Avis (2007)
Antoine Deza Mcgill, David Avis, Antoine Deza
The solitaire cone SB is the cone of all feasible fractional Solitaire Peg games. Valid inequalities over this cone, known as pagoda functions, were used to show the infeasibility of various peg...
Hyperplane Arrangements with Large Average Diameter (2007)
The largest possible average diameter of a bounded cell of a simple hyperplane arrangement is conjectured to be not greater than the dimension. We prove that this conjecture holds in dimension 2, and...
The complexity of the envelope of line and plane arrangements (2007)
Bremner, David, Deza, Antoine, Xie, Feng
A facet of an hyperplane arrangement is called external if it belongs to exactly one bounded cell. The set of all external facets forms the envelope of the arrangement. The number of external facets...
Hyperplane arrangements with large average diameter, AdvOLReport 2007/01 (2007)
Antoine Deza, Feng Xie, Antoine Deza, Feng Xie
Abstract: Let ∆A(n, d) denote the largest possible average diameter of a bounded cell of a simple arrangement defined by n hyperplanes in dimension d. We have ∆A(n, 2) ≤ 2 + 2 n−1 in the...
Hyperplane arrangements with large average diameter, AdvOLReport 2007/01 (2007)
Antoine Deza, Feng Xie, Antoine Deza, Feng Xie
Abstract: The largest possible average diameter of a bounded cell of a simple hyperplane arrangement is conjectured to be not greater than the dimension. We prove that this conjecture holds in...
The continuous d-step conjecture for polytopes (2007)
Antoine Deza, Tamás Terlaky, Yuriy Zinchenko, Antoine Deza, Tamás Terlaky, Yuriy Zinchenko
The curvature of a polytope, defined as the largest possible total curvature of the associated central path, can be regarded as the continuous analogue of its diameter. We prove the analogue of the...
The complexity of the envelope of line and plane arrangements (2007)
David Bremner, Antoine Deza, Feng Xie, David Bremner, Antoine Deza, Feng Xie
The complexity of the envelope
Colourful Simplicial Depth (2006)
Antoine Deza, Sui Huang, Tamon Stephen, Tamás Terlaky, Carathéodory Theorem
s14
Antoine Deza, Chris Dickson, Tamás Terlaky, Anthony Vanelli, Hu Zhang, Sui Chris Huang
Future Work
ORIGINAL PAPER A counterexample to the dominating set conjecture (2006)
Abstract The metric polytope metn is the polyhedron associated with all semimetrics on n nodes and defined by the triangle inequalities xij − xik − xjk ≤ 0 and xij + xik + xjk ≤ 2 for all...
D.: The isometries of the cut, metric and hypermetric cones (2006)
Antoine Deza, Boris Goldengorin, Dmitrii V. Pasechnik
We show that the symmetry groups of the cut cone Cutn and the metric cone Metn both consist of the isometries induced by the permutations on {1,..., n}; that is, Is(Cutn) = Is(Metn) � Sym(n) for n...
In 1966, Claude Berge proposed the following sorting problem. Given a string of $n$ alternating white and black pegs on a one-dimensional board consisting of an unlimited number of empty holes,...
A counterexample to a conjecture of Laurent and Poljak (2005)
The metric polytope m(n) is the polyhedron associated with all semimetrics on n nodes. In 1992 Monique Laurent and Svatopluk Poljak conjectured that every fractional vertex of the metric polytope is...
The Colourful Feasibility Problem (2005)
Deza, Antoine, Huang, Sui, Stephen, Tamon, Terlaky, Tamás
We study a colourful generalization of the linear programming feasibility problem, comparing the algorithms introduced by Barany and Onn with new methods. We perform benchmarking on generic and...
Colourful Simplicial Depth (2005)
Deza, Antoine, Huang, Sui, Stephen, Tamon, Terlaky, Tamás
Inspired by Barany's colourful Caratheodory theorem, we introduce a colourful generalization of Liu's simplicial depth. We prove a parity property and conjecture that the minimum colourful simplicial...
The central path visits all the vertices of the Klee–Minty cube (2005)
Publisher Taylor, Registered Engl, Wales Registered Number, Antoine Deza, Eissa Nematollahi, Reza Peyghami, ...
Publication details, including instructions for authors and subscription information:
The isometries of the cut, metric and hypermetric cones (2003)
Deza, Antoine, Goldengorin, Boris, Pasechnik, Dmitrii V.
We show that the symmetry groups of the cut cone Cut(n) and the metric cone Met(n) both consist of the isometries induced by the permutations on {1,...,n}; that is, Is(Cut(n))=Is(Met(n))=Sym(n) for...
The isometries of the cut, metric and hypermetric cones (2003)
Deza, Antoine, Goldengorin, Boris, Pasechnik, Dmitrii V.
We discuss integrated chance constraints in their role of short-term risk constraints in a strategic ALM model for Dutch pension funds. The problem is set up as a multistage recourse model, with...
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...
On the skeleton of the metric polytope (2001)
Antoine Deza, Komei Fukuda, Dimitrii Pasechnik, Masanori Sato
We consider polyhedra with applications to well-know combinatorial optimization problems: the metric polytope mn and its relatives. For n 6 the description of the metric polytope is easy as mn has at...
On the Solitaire Cone and Its Relationship to (2001)
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. The modern mathematical study of the game dates to...
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...
Necessary Conditions for Solitaire Feasibility (1999)
. 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 peg...
Fullerenes and coordination polyhedra versus half-cube embeddings, Discrete Math (1998)
Antoine Deza, Michel Deza, Viatcheslav Grishukhin
A fullerene F n is a 3-regular (or cubic) polyhedral carbon molecule for which the n vertices-the carbons atoms- are arranged in 12 pentagons and ( n
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...
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. The modern mathematical study of the game dates to...
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. The modern mathematical study of the game dates to...
On Skeletons, Diameters and Volumes of Metric Polyhedra (1996)
Uperieure S Ormale, N Ecole, Antoine Deza, Antoine Deza, Michel Deza, Michel Deza, ...
. We survey and present new geometric and combinatorial properties of some polyhedra with application in combinatorial optimization, for example, the max-cut and multicommodity flow problems. Namely...
The Combinatorial Structure of Small Cut and Metric Polytopes (1995)
Antoine Deza, Antoine Deza, Michel Deza, Michel Deza
. We study the combinatorial structure of the cut and metric polytopes on n nodes for n 5. Those two polytopes have a complicated geometrical structure, but using their large symmetry group, we can...
On the skeleton of the dual cut polytope (1994)
Abstract. The cut polytope is the \Gamma n
The Combinatorial Structure of Small Cut and Metric Polytopes (1994)
. We study the combinatorial structure of the cut and metric polytopes on n nodes for n 5. Those two polytopes have a complicated geometrical structure, but using their large symmetry group, we can...
The isometries of the cut, metric and hypermetric cones
Deza, Antoine, Goldengorin, Boris, Pasechnik, Dmitrii V.
We discuss integrated chance constraints in their role of short-term risk constraints in a strategic ALM model for Dutch pension funds. The problem is set up as a multistage recourse model, with...