22 citations
- Courant Institute of Mathematical SciencesUS2 papers
- University of California, DavisUS2 papers
- University of Illinois Urbana-ChampaignUS2 papers
- Harvard University PressUS1 paper
- Hebrew University of JerusalemIL1 paper
- IIT@MITUS1 paper
- Large Synoptic Survey Telescope CorporationUS1 paper
- Lowell ObservatoryUS1 paper
- Massachusetts Institute of TechnologyUS1 paper
- Microsoft Research (India)IN1 paper
- Princeton UniversityUS1 paper
- Rensselaer Polytechnic InstituteUS1 paper
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2008★ 5 cited
Phase transition for Local Search on planted SAT
Andrei A. Bulatov, Evgeny S. Skvortsov
The Local Search algorithm (or Hill Climbing, or Iterative Improvement) is one of the simplest heuristics to solve the Satisfiability and Max-Satisfiability problems. It is a part…
cs.DS2008★ 3 cited
Algorithms for Secretary Problems on Graphs and Hypergraphs
Nitish Korula, Martin Pal
We examine several online matching problems, with applications to Internet advertising reservation systems. Consider an edge-weighted bipartite graph G, with partite sets L, R. We…
cs.DS2007
Radix Sorting With No Extra Space
Gianni Franceschini, S. Muthukrishnan, Mihai Patrascu
It is well known that n integers in the range [1,n^c] can be sorted in O(n) time in the RAM model using radix sorting. More generally, integers in any range [1,U] can be sorted in…