3k citations
- Istituto Nazionale di Fisica Nucleare, Laboratori Nazionali di FrascatiIT882 papers
- Peking UniversityCN825 papers
- Institute of High Energy PhysicsCN730 papers
- Massachusetts Institute of TechnologyUS701 papers
- Istituto Nazionale di Fisica Nucleare, Sezione di PerugiaIT698 papers
- National Centre for Nuclear ResearchPL690 papers
- Tsinghua UniversityCN689 papers
- Fermi National Accelerator LaboratoryUS673 papers
- The Ohio State UniversityUS657 papers
- Beihang UniversityCN651 papers
- Joint Institute for Nuclear ResearchRU644 papers
- University of TurinIT643 papers
7 papers · 2 filters
Improved Region-Growing and Combinatorial Algorithms for -Route Cut Problems
Guru Guruganesh, Laura Sanita, Chaitanya Swamy
We study the {\em -route} generalizations of various cut problems, the most general of which is \emph{-route multicut} (-MC) problem, wherein we have source-sink pairs…
Consistent Weighted Sampling Made Fast, Small, and Easy
Bernhard Haeupler, Mark Manasse, Kunal Talwar
Document sketching using Jaccard similarity has been a workable effective technique in reducing near-duplicates in Web page and image search results, and has also proven useful in…
Near-Optimum Online Ad Allocation for Targeted Advertising
Joseph, Naor, David Wajc
Motivated by Internet targeted advertising, we address several ad allocation problems. Prior work has established these problems admit no randomized online algorithm better than $(…
Ignorance is Almost Bliss: Near-Optimal Stochastic Matching With Few Queries
Avrim Blum, John P. Dickerson, Nika Haghtalab +3
The stochastic matching problem deals with finding a maximum matching in a graph whose edges are unknown but can be accessed via queries. This is a special case of stochastic -s…
Constant Factor Approximation for Balanced Cut in the PIE model
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
We propose and study a new semi-random semi-adversarial model for Balanced Cut, a planted model with permutation-invariant random edges (PIE). Our model is much more general than p…
On Integrality Ratios for Asymmetric TSP in the Sherali-Adams Hierarchy
Joseph Cheriyan, Zhihan Gao, Konstantinos Georgiou +1
We study the ATSP (Asymmetric Traveling Salesman Problem), and our focus is on negative results in the framework of the Sherali-Adams (SA) Lift and Project method. Our main result…