- Series
- ACO Student Seminar
- Time
- Friday, September 18, 2020 - 1:00pm for 1 hour (actually 50 minutes)
- Location
- https://bluejeans.com/264244877/0166
- Speaker
- Majid Farhadi – CS, Georgia Tech – majid.farhadi94@gmail.com – https://scholar.google.com/citations?user=iyX9zQsAAAAJ&hl=en
- Organizer
- He Guo
We present a new rounding framework and improve the approximation bounds for min sum vertex cover and generalized min sum set cover, also known as multiple intents re-ranking problem. These classical combinatorial optimization problems find applications in scheduling, speeding up semidefinite-program solvers, and query-results diversification, among others.
Our algorithm is based on transforming the LP solution by a suitable kernel and applying a randomized rounding. It also gives a linear-programming based 4-approximation algorithm for min sum set cover, i.e., best possible due to Feige, Lovász, and Tetali. As part of the analysis of our randomized algorithm we derive an inequality on the lower tail of a sum of independent Bernoulli random variables, which may be of independent interest.
Joint work with Nikhil Bansal, Jatin Batra, and Prasad Tetali. [arXiv:2007.09172]