Testing polyhedral properties and approximation algorithms for hard optimization problems

linear inequalities, or by a finite set of extreme points and extreme
rays. In combinatorial optimization, a polyhedron representing the set of
linear relaxations of the feasible solutions, of a given problem, is
usually available in the first form, but certain properties of the extreme
points play an important role in the quality of the solution obtained from
this relaxation. We first argue that testing some of these properties is
generally hard. Then, we give an example from geometry, where such
properties can be exploited to get a good approximate solution for an
NP-hard optimization problem. Finally, we consider the problem of picking,
from a given system of linear inequalities, the maximum subset such that
the polyhedron defined by it is non-empty, and give some positive and
negative results and some applications.