Minimum linear ordering problems under submodular costs

Combinatorics Seminar
Friday, September 21, 2012 - 15:05
1 hour (actually 50 minutes)
Skiles 005
Georgia Tech
 We introduce a general Minimum Linear Ordering Problem (MLOP): Given a nonnegative set function f on a finite set V, find a linear ordering on V such that the sum of the function values for all the suffixes is minimized. This problem generalizes well-known problems such as the Minimum Linear Arrangement, Min Sum Set Cover, and Multiple Intents Ranking. Extending a result of Feige, Lovasz, and Tetali (2004) on Min Sum Set Cover, we show that the greedy algorithm provides a factor 4 approximate optimal solution when the cost function f is supermodular. We also present a factor 2 rounding algorithm for MLOP with a monotone submodular cost function, while the non monotone case remains wide open.  This is joint work with Satoru Iwata and Pushkar Tripathi.