Atlas home || Conferences | Abstracts | about Atlas

Joint Meeting of AMS, DMV, and ÖMG
June 16-19, 2005
Johannes Gutenberg University
Mainz, Germany

Organizers
Volker Bach, Mainz; Klaus D. Bierstedt, DMV; Susan Friedlander, Associate Secretary, AMS

View Abstracts
Conference Homepage

Linear Programming and Unique Sink Orientations
by
Bernd Gärtner
Institute of Theoretical Computer Science, ETH Zürich, CH-8092 Zürich, Switzerland
Coauthors: Ingo Schurr

I will introduce the framework of unique sink orientations (USO) as a new tool for dealing with linear programs (LP). For certain LP, the USO approach yields the fastest known deterministic combinatorial algorithm. We also obtain a unique canonical solution for any LP, even in the unbounded or the infeasible case. Connections to quadratic programs and certain linear complementarity problems will be pointed out

Date received: January 17, 2005

Copyright © 2005 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caoz-42.