Séance MA10 - Calcul polyédrique I / Polyhedral Computation I
Jour lundi, le 04 mai 2009 Salle Dutailier International Président David Avis
Présentations
|
10h30- 10h55 |
On the Hardness of Approximating the Vertex-Centroid of a Polyhedron |
|
Khaled Elbassioni, Max-Planck Institute for Computer Science, Algorithms and Complexity, Campus E 1 4, Saarbruecken, Germany, 66111 We show for unbounded polyhedra in R^d, there is no polynomial-time algorithm for approximating the vertex-centroid (which is the average of the vertices) to within a distance of d^{1/2-\delta}, for any fixed \delta>0, unless P=NP. |
|
10h55- 11h20 |
Self-Duality of Polytopes: Complexity, and Relation to Vertex Enumeration |
|
Hans Raj Tiwary, Technische Universität Berlin, Institut für Mathematik, MA 6-2, Straße des 17. Juni, 136, Berlin, Berlin, Germany, 10623 We discuss the computational complexity of checking whether a polytope is combinatorially isomorphic to its polar dual. We show that for polytopes represented by both facets and vertices this is equivalent to graph-isomorphism problem, and for polytopes represented by either only facets or only vertices it is equivalent to graph-isomorphism if vertex enumeration is graph-isomorphism-easy. |
|
11h20- 11h45 |
Developing an Exact Solver for Multi-Parametric LCPs with Sufficient Matrices |
|
David Adjiashvili, ETH, Zurich, MATH Colin N. Jones, ETH, Zurich Komei Fukuda, ETH, Zurich We develop an exact solver for the multi-parametric Linear Complementarity Problem (pLCP) with sufficient matrices. Our current C++ implementation uses the GNU Multiple Precision arithmetic library for exact rational arithmetic, the C Double Description library for solving linear programming exactly and the Linbox library as a linear algebra package. Object oriented desige is used to facilitate modularity and extendability. |