Abstract Objective Function Graphs on the 3-cube: A Classification by Realizability

Gärtner, Bernd and Kaibel, Volker (1998) Abstract Objective Function Graphs on the 3-cube: A Classification by Realizability.
Technical Report , 12 p.

Abstract

We call an orientation of the graph of a simple polytope P an abstract objective function (AOF) graph if it satisfies two conditions that make the simplex algorithm (e.g. with the Random-Facet pivot rule of Kalai and Matousek, Sharir, and Welzl) work: it has to be acyclic and it has to induce a unique sink in every subgraph that corresponds to a face of the polytope. For the graph of the 3-dimensional cube we investigate the question which among all possible AOF graphs are realizable in the sense that they are induced by some linear program (with a polytope of feasible solutions that is combinatorially a 3-dimensional cube). It turns out that (up to isomorphism) precisely two AOF graphs are not realizable.


Actions:
Download: [img] Postscript
Download (241kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr98-318
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 16 Jan 2012 15:42
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/318