Amazon cover image
Image from Amazon.com

Polyhedral computation

Contributor(s): Material type: TextTextSeries: CRM proceedings & lecture notes; 48Publication details: American Mathematical Society 2009 ProvidenceDescription: ix, 147 p.: col. ill. Includes bibliographical referencesISBN:
  • 9780821846339
Subject(s): DDC classification:
  • 516.156 P6
Summary: Many polytopes of practical interest have enormous output complexity and are often highly degenerate, posing severe difficulties for known general-purpose algorithms. They are, however, highly structured, and attention has turned to exploiting this structure, particularly symmetry. Initial applications of this approach have permitted computations previously far out of reach, but much remains to be understood and validated experimentally. The papers in this volume give a good snapshot of the ideas discussed at a Workshop on Polyhedral Computation held at the CRM in Montreal in October 2006 and, with one exception, the current state of affairs in this area. The exception is the inclusion of an often cited 1980 technical report of Norman Zadeh, which was never published in a journal and has passed into the folklore of the discipline. This paper illustrates beautifully the work still to be done in the field: it gives a simple pivot rule for the simplex method for which it is still unknown if it yields a polynomial time algorithm. https://bookstore.ams.org/crmp-48/
Tags from this library: No tags from this library for this title. Log in to add tags.
Star ratings
    Average rating: 0.0 (0 votes)
Holdings
Item type Current library Item location Collection Shelving location Call number Status Date due Barcode
Books Vikram Sarabhai Library Rack 28-A / Slot 1384 (0 Floor, East Wing) Non-fiction General Stacks 516.156 P6 (Browse shelf(Opens below)) Available 203269

Table of content

On Combinatorial Properties of Linear Program Digraphs
Generating Vertices of Polyhedra and Related Problems of Monotone Generation
Polyhedral Representation Conversion up to Symmetries
An Output-Sensitive Algorithm for Multi-Parametric LCPs with Sufficient
Hyperplane Arrangements with Large Average Diameter
Enumerating the Nash Equilibria of Rank-1 Games
What is the Worst Case Behavior of the Simplex Algorithm?
Postcript to "What is the Worst Case Behavior of the Simplex Algorithm?"

Many polytopes of practical interest have enormous output complexity and are often highly degenerate, posing severe difficulties for known general-purpose algorithms. They are, however, highly structured, and attention has turned to exploiting this structure, particularly symmetry. Initial applications of this approach have permitted computations previously far out of reach, but much remains to be understood and validated experimentally. The papers in this volume give a good snapshot of the ideas discussed at a Workshop on Polyhedral Computation held at the CRM in Montreal in October 2006 and, with one exception, the current state of affairs in this area. The exception is the inclusion of an often cited 1980 technical report of Norman Zadeh, which was never published in a journal and has passed into the folklore of the discipline. This paper illustrates beautifully the work still to be done in the field: it gives a simple pivot rule for the simplex method for which it is still unknown if it yields a polynomial time algorithm.

https://bookstore.ams.org/crmp-48/

There are no comments on this title.

to post a comment.