On Linear Relaxations for Linear OrderingsAlantha NewmanMIT
November 1,

ABSTRACT


The linear ordering problem is easy to state: given a complete weighted directed graph on $n$ nodes, find a spanning acyclic tournament of maximum weight (i.e. a maximum acyclic subgraph). Although the problem is NPhard, it is easy to estimate the optimum to within a factor of 2 (take any linear ordering L; the spanning acyclic tournament consistent with either L or the opposite ordering L' has weight at least half the maximum). It is not known whether the maximum can be estimated to a better factor using a polynomialtime algorithm. In this talk, we discuss widelystudied polyhedral relaxations for this problem. The integrality gap of a relaxation is the extremal ratio between the estimate provided by the relaxation and the true optimum. We show that the integrality gap for the basic linear relaxation (solvable in polynomialtime) is 2 and that this gap remains 2 even when the relaxation is strengthened by the socalled "fence" constraints. Our proof is nonconstructive we demonstrate an extremal example via the probabilistic method. Finally, we show that no relaxation that is solvable in polytime can have an integrality gap less than 66/65 unless P=NP. This is joint work with Santosh Vempala. 
Combinatorics Seminar, Mathematics Department, MIT, sara(atsign)math.mit.edu 

