Primal—Dual Methods for Vertex and Facet Enumeration |
| |
Authors: | D Bremner K Fukuda A Marzetta |
| |
Institution: | (1) Department of Mathematics, University of Washington, Seattle, WA 98195, USA bremner@math.washington.edu, US;(2) Department of Mathematics, Swiss Federal Institute of Technology, Lausanne, Switzerland , CH;(3) Institute for Operations Research, Swiss Federal Institute of Technology, Zurich, Switzerland fukuda@ifor.math.ethz.ch, CH;(4) Institute for Theoretical Computer Science, Swiss Federal Institute of Technology, Zurich, Switzerland marzetta@inf.ethz.ch, CH |
| |
Abstract: | Every convex polytope can be represented as the intersection of a finite set of halfspaces and as the convex hull of its
vertices. Transforming from the halfspace (resp. vertex) to the vertex (resp. halfspace) representation is called vertex enumeration (resp. facet enumeration ). An open question is whether there is an algorithm for these two problems (equivalent by geometric duality) that is polynomial
in the input size and the output size. In this paper we extend the known polynomially solvable classes of polytopes by looking
at the dual problems. The dual problem of a vertex (resp. facet) enumeration problem is the facet (resp. vertex) enumeration problem for the same polytope
where the input and output are simply interchanged. For a particular class of polytopes and a fixed algorithm, one transformation
may be much easier than its dual. In this paper we propose a new class of algorithms that take advantage of this phenomenon.
Loosely speaking, primal—dual algorithms use a solution to the easy direction as an oracle to help solve the seemingly hard direction.
Received July 31, 1997, and in revised form March 8, 1998. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|