Seminars & Colloquia Calendar
Set Cover in Sub-linear Time
Sepideh Mahabadi, Columbia University
Location: CoRE 301
Date & time: Wednesday, 07 March 2018 at 11:00AM - 12:00PM
Abstract: Given access to a collection of \(m\) sets over a ground set of \(n\) elements, the classic set cover problem asks for the minimum number of sets in the collection that cover all the elements. We study this problem from the perspective of sub-linear algorithms, where the input can be accessed by querying either the ith element contained in a set, or the jth set containing an element. In this work, we present sub-linear algorithms for the set cover problem and show that they achieve almost tight query complexities.
More specifically, on the one hand, we show an algorithm that returns an \(alpha\)-approximate cover using \(tilde O(m(n/k)^{1/(alpha-1)} + nk)\) queries to the input, where \(k\) denotes the value of a minimum set cover. We then complement this upper bound by proving that for lower values of \(k\), the required number of queries is \(tilde Omega(m(n/k)^{1/(2alpha)})\). Moreover, we prove that even checking whether a given collection of sets covers all the elements would require \(Omega(nk)\) queries. These two lower bounds provide strong evidence that the upper bound is almost tight for certain values of the parameter \(k\). On the other hand, we show that this bound is not optimal for larger values of the parameter \(k\), as there exists a \((1+eps)\)-approximation algorithm with \(tilde O(mn/keps^2)\) queries. We show that this bound is also essentially tight by establishing a lower bound of \(tilde Omega(mn/k)\).
This is a joint work with Piotr Indyk, Ronitt Rubinfeld, Ali Vakilian, and Anak Yodpinyanee.
R. Shapiro Organizer's Page
Charles Weibel Organizer's Page
Brooke Logan
Wujun Zhang Organizer's webpage
P. Gupta, X.Huang and J. Song Organizer's webpage
Swastik Kopparty, Sepehr Assadi Seminar webpage
Jeffry Kahn, Bhargav Narayanan, Jinyoung Park Organizer's webpage
Yonah Biers-Ariel, Mingjia Yang, and Doron Zeilberger --> homepage
Paul Feehan, Manousos Maridakis, Natasa Sesum Organizer's webpage
Lev Borisov, Emanuel Diaconescu, Angela Gibney, Nicolas Tarasca, and Chris Woodward Organizer's webpage
Jason Saied Seminar webpage
Brian Pinsky, Rashmika Goswami website
Corrine Yap Organizer's webpage
Edna Jones Organizer's webpage
Yanyan Li, Zheng-Chao Han, Jian Song, Natasa Sesum
Lisa Carbone, Yi-Zhi Huang, James Lepowsky, Siddhartha Sahi Organizer's webpage
Simon Thomas website
Kasper Larsen, Daniel Ocone and Kim Weston Organizer's page
Joel Lebowitz, Michael Kiessling
Yanyan Li, Haim Brezis
Brooke Ogrodnik website
Stephen D. Miller, John C. Miller, Alex V. Kontorovich, Claire Burrin seminar website
Stephen D. Miller
Organizers: Yanyan Li, Z.C. Han, Jian Song, Natasa Sesum
Yael Davidov Seminar webpage
Kristen Hendricks, Xiaochun Rong, Hongbin Sun, Chenxi Wu Organizer's page
Ebru Toprak, Organizer
Organizer: Luochen Zhao
James Holland; Organizer website
Organizer: Vladimir Retakh Organizer's webpage
- Show events from all categories
Special Note to All Travelers
Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.
Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.