Item Successfully Added to Cart
An error was encountered while trying to add the item to the cart. Please try again.
OK
Please make all selections above before adding to cart
OK
The following link can be shared to navigate to this page. You can select the link to copy or click the 'Copy To Clipboard' button below.
Copy To Clipboard
Successfully Copied!
Polyhedral Computation
 
Edited by: David Avis McGill University, Montréal, QC, Canada
David Bremner University of New Brunswick, Fredericton, NB, Canada
Antoine Deza McMaster University, Hamilton, ON, Canada
A co-publication of the AMS and Centre de Recherches Mathématiques
Front Cover for Polyhedral Computation
Available Formats:
Softcover ISBN: 978-0-8218-4633-9
Product Code: CRMP/48
List Price: $84.00
MAA Member Price: $75.60
AMS Member Price: $67.20
Electronic ISBN: 978-1-4704-1774-1
Product Code: CRMP/48.E
List Price: $79.00
MAA Member Price: $71.10
AMS Member Price: $63.20
Bundle Print and Electronic Formats and Save!
This product is available for purchase as a bundle. Purchasing as a bundle enables you to save on the electronic version.
List Price: $126.00
MAA Member Price: $113.40
AMS Member Price: $100.80
Front Cover for Polyhedral Computation
Click above image for expanded view
  • Front Cover for Polyhedral Computation
  • Back Cover for Polyhedral Computation
Polyhedral Computation
Edited by: David Avis McGill University, Montréal, QC, Canada
David Bremner University of New Brunswick, Fredericton, NB, Canada
Antoine Deza McMaster University, Hamilton, ON, Canada
A co-publication of the AMS and Centre de Recherches Mathématiques
Available Formats:
Softcover ISBN:  978-0-8218-4633-9
Product Code:  CRMP/48
List Price: $84.00
MAA Member Price: $75.60
AMS Member Price: $67.20
Electronic ISBN:  978-1-4704-1774-1
Product Code:  CRMP/48.E
List Price: $79.00
MAA Member Price: $71.10
AMS Member Price: $63.20
Bundle Print and Electronic Formats and Save!
This product is available for purchase as a bundle. Purchasing as a bundle enables you to save on the electronic version.
List Price: $126.00
MAA Member Price: $113.40
AMS Member Price: $100.80
  • Book Details
     
     
    CRM Proceedings & Lecture Notes
    Volume: 482009; 147 pp
    MSC: Primary 52; 90;

    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 Montréal 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.

    Readership

    Graduate students and research mathematicians interested in discrete and computational geometry, combinatorial and continuous optimization, linear programming, enumeration algorithms, and computational complexity.

  • Table of Contents
     
     
    • Chapters
    • 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 matrices
    • Hyperplane arrangements with large average diameter
    • Enumerating the Nash equilibria of rank-1 games
    • What is the worst case behavior of the simplex algorithm?
    • Postscript to "What is the worst case behavior of the simplex algorithm?"
  • Additional Material
     
     
  • Request Review Copy
Volume: 482009; 147 pp
MSC: Primary 52; 90;

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 Montréal 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.

Readership

Graduate students and research mathematicians interested in discrete and computational geometry, combinatorial and continuous optimization, linear programming, enumeration algorithms, and computational complexity.

  • Chapters
  • 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 matrices
  • Hyperplane arrangements with large average diameter
  • Enumerating the Nash equilibria of rank-1 games
  • What is the worst case behavior of the simplex algorithm?
  • Postscript to "What is the worst case behavior of the simplex algorithm?"
You may be interested in...
Please select which format for which you are requesting permissions.