Algorithms, Combinatorics and Optimization Seminar
— 4:30pm
Location:
In Person

Wean Hall 8220
Speaker:
MAJID FARHADI
,
Ph.D. Student, Algorithms, Combinatorics and Optimization
http://majidfarhadi.github.io/
On Submodular Minimum Linear Ordering
A Minimum Linear Ordering Problem (MLOP) is an optimization over orderings/permutations of a finite set, given along with a nonnegative (cost) function f, with the objective of minimizing the aggregated values of f over prefixes of the ordering. This is in contrast to the classical phenomenon of minimizing a cost function over combinatorial subsets, e.g., the minimum set cover versus the MLOP counterpart of minimum sum set cover, introduced by Feige, Lov ́asz, and Tetali in 2004. While the more general MLOP for supermodular cost functions is also 4 approximable [ITT 12] using a greedy algorithm that is further NPhard to improve [FLT 04]; the approximability of submodular (cost function) MLOP remains less resolved. For the monotone submodular MLOP, we present a 2(1+L)/(n+1) approximation, where L can be interpreted as a measure of linearity of f, using a different approach and refining upon the 22/(n+1) approximation by Iwata, Tetali, and Tripathi. We further show the problem remains NPhard, even for the special case of f being the rank of a (graphic) matroid, and discuss connections to and open problems in the literature.
This work is joint work with Swati Gupta, Shengding Sun, Prasad Tetali, and Michael Wigal.
Event Website:
https://aco.math.cmu.edu/seminar.html
For More Information:
anewman@andrew.cmu.edu