On Linear Relaxations for Linear Orderings

Alantha Newman


November 1,
refreshments at 3:45pm


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 NP-hard, 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 polynomial-time algorithm.

In this talk, we discuss widely-studied 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 polynomial-time) is 2 and that this gap remains 2 even when the relaxation is strengthened by the so-called "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 poly-time can have an integrality gap less than 66/65 unless P=NP.

This is joint work with Santosh Vempala.

Speaker's Contact Info: alantha(at-sign)theory.lcs.mit.edu

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)math.mit.edu

Page loaded on October 26, 2000 at 01:48 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.