default search action
20th SODA 2009: New York, NY, USA
- Claire Mathieu:
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009. SIAM 2009, ISBN 978-0-89871-680-1 - Gabriel Nivasch
:
Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations. 1-10 - Ashish Goel, Michael Kapralov
Perfect matchings via uniform sampling in regular bipartite graphs. 11-17 - Ashish Goel, Sanjeev Khanna, Brad Null:
The ratio index for budgeted learning, with applications. 18-27 - Sudipto Guha, Kamesh Munagala
Approximation algorithms for restless bandit problems. 28-37 - Elad Hazan, Satyen Kale:
Better algorithms for benign bandits. 38-47 - Colin Cooper, Alan M. Frieze:
The cover time of random geometric graphs. 48-57 - Ilia Binder, Mark Braverman:
The complexity of simulating Brownian Motion. 58-67 - Sergi Elizalde, Peter Winkler:
Sorting by placement and shift. 68-75 - Sam Greenberg, Amanda Pascoe, Dana Randall:
Sampling biased lattice configurations using exponential metrics. 76-85 - Frédéric Magniez, Ashwin Nayak, Peter C. Richter, Miklos Santha:
On the hitting times of quantum versus random walks. 86-95 - Alon Shalita, Uri Zwick:
Efficient algorithms for the 2-gathering problem. 96-105 - Michael Molloy, Bruce A. Reed:
Asymptotically optimal frugal colouring. 106-114 - Stéphan Thomassé:
A quadratic kernel for feedback vertex set. 115-119 - Zdenek Dvorák, Daniel Král, Robin Thomas:
Coloring triangle-free graphs on surfaces. 120-129 - Michael Drmota, Wojciech Szpankowski:
(Un)expected behavior of digital search tree profile. 130-138 - Michael I. Jordan:
Combinatorial stochastic processes and nonparametric Bayesian modeling. 139 - Timothy M. Chan:
Comparison-based time-space lower bounds for selection. 140-149 - David Eppstein, Michael T. Goodrich
Linear-time algorithms for geometric graphs with sublinearly many crossings. 150-159 - David Eppstein, Elena Mumford:
Self-overlapping curves revisited. 160-169 - Haim Kaplan, Natan Rubin, Micha Sharir:
Line transversals of convex polyhedra in R3. 170-179 - Peyman Afshani, Timothy M. Chan:
Optimal halfspace range reporting in three dimensions. 180-186 - J. Salez, D. Shah:
Optimality of belief propagation for random assignment problem. 187-196 - Krishnendu Chatterjee, Luca de Alfaro, Thomas A. Henzinger:
Termination criteria for solving concurrent safety and reachability games. 197-206 - Amin Coja-Oghlan, Colin Cooper, Alan M. Frieze:
An efficient sparse regularity concept. 207-216 - Yury Person
Almost all hypergraphs without Fano planes are bipartite. 217-226 - Brendan Nagle, Annika Poerschke, Vojtech Rödl, Mathias Schacht:
Hypergraph regularity and quasi-randomness. 227-235 - Philip N. Klein, Shay Mozes
Shortest paths in directed planar graphs with negative lengths: a linear-space O(n log2 n)-time algorithm. 236-245 - David R. Karger
A near-linear time algorithm for constructing a cactus representation of minimum cuts. 246-255 - Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio:
Testing halfspaces. 256-264 - Anand Bhalgat, Ramesh Hariharan:
Fast edge orientation for unweighted graphs. 265-272 - Omid Amini, Louis Esperet
A unified approach to distance-two colouring of planar graphs. 273-282 - Pankaj K. Agarwal, R. Sharathkumar, Hai Yu:
Approximate Euclidean shortest paths amid convex obstacles. 283-292 - Alexandr Andoni, Piotr Indyk, Robert Krauthgamer, Huy L. Nguyen:
Approximate line nearest neighbor in high dimensions. 293-301 - Greg Aloupis, Jean Cardinal, Sébastien Collette, Stefan Langerman, David Orden, Pedro Ramos:
Decomposition of multiple coverings into more parts. 302-310 - Adrian Dumitrescu, Csaba D. Tóth, Guangwu Xu:
On stars and Steiner stars: II. 311-317 - Yury Lifshits, Shengyu Zhang:
Combinatorial algorithms for nearest neighbors, near-duplicates and small-world design. 318-326 - Edith Elkind, Dmitrii V. Pasechnik
Computing the nucleolus of weighted voting games. 327-335 - Ehsan Amiri, Gábor Tardos:
High rate fingerprinting codes and the fingerprinting capacity. 336-345 - Noga Alon, Uriel Feige:
On the power of two, three and four probes. 346-354 - Toniann Pitassi, Nathan Segerlind:
Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures. 355-364 - Ryan O'Donnell, Yi Wu:
3-bit dictator testing: 1 vs. 5/8. 365-373 - Markus Chimani, Carsten Gutwenger, Petra Mutzel
Inserting a vertex into a planar graph. 375-383 - Ran Duan, Seth Pettie:
Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths. 384-391 - Constantinos Daskalakis, Richard M. Karp, Elchanan Mossel, Samantha J. Riesenfeld
Sorting and selection in posets. 392-401 - Parikshit Gopalan, Jaikumar Radhakrishnan:
Finding duplicates in a data stream. 402-411 - Ping Li:
Compressed counting. 412-421 - Bernard Chazelle:
Natural algorithms. 422-431 - Konstantinos Panagiotou, Angelika Steger:
Maximal biconnected subgraphs of random planar graphs. 432-440 - James Aspnes, Keren Censor:
Approximate shared-memory counting despite a strong adversary. 441-450 - Amin Coja-Oghlan, Uriel Feige, Alan M. Frieze, Michael Krivelevich, Dan Vilenchik:
On smoothed k-CNF formulas and the Walksat algorithm. 451-460 - Bodo Manthey, Heiko Röglin
Improved smoothed analysis of the k-means method. 461-470 - Amr Elmasry:
Pairing heaps with O(log log n) decrease cost. 471-476 - Haim Kaplan, Uri Zwick:
A simpler implementation and analysis of Chazelle's soft heaps. 477-485 - Vida Dujmovic, John Howat, Pat Morin
Biased range trees. 486-495 - Erik D. Demaine, Dion Harmon, John Iacono, Daniel Kane, Mihai Patrascu:
The geometry of binary search trees. 496-505 - Ran Duan, Seth Pettie:
Dual-failure distance and connectivity oracles. 506-515 - Viswanath Nagarajan, Maxim Sviridenko:
On the maximum quadratic assignment problem. 516-524 - Prasad Raghavendra, David Steurer
Towards computing the Grothendieck constant. 525-534 - Michel X. Goemans, Nicholas J. A. Harvey, Satoru Iwata, Vahab S. Mirrokni:
Approximating submodular functions everywhere. 535-544 - Ariel Kulik, Hadas Shachnai, Tami Tamir:
Maximizing submodular set functions subject to multiple linear constraints. 545-554 - Aurore Amaudruz, Christina Fragouli:
Combinatorial algorithms for wireless information flow. 555-564 - Volker Strassen:
Probability, algorithms and complexity. 565 - Mohsen Bayati, Andrea Montanari, Amin Saberi:
Generating random graphs with large girth. 566-575 - Navin Goyal, Luis Rademacher
Expanders via random spanning trees. 576-585 - Lorenz Minder, Alistair Sinclair:
The extended k-tree algorithm. 586-595 - David Gamarnik, Dmitriy Katz:
Sequential cavity method for computing limits of the log-partition function for lattice models. 596-605 - Serge Gaspers, Gregory B. Sorkin
A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between. 606-615 - Sergio Cabello:
Finding shortest contractible and shortest separating cycles in embedded graphs. 616-624 - Alexander Golynski:
Cell probe lower bounds for succinct data structures. 625-634 - Prosenjit Bose, Eric Y. Chen, Meng He
Succinct geometric indexes supporting point location queries. 635-644 - Kevin Buchin, Maike Buchin, Yusu Wang:
Exact algorithms for partial curve matching via the Fréchet distance. 645-654 - Mikkel Thorup:
String hashing for linear probing. 655-664 - Klaus Jansen:
Parameterized approximation scheme for the multiple knapsack problem. 665-674 - Florian Diedrich, Klaus Jansen:
Improved approximation algorithms for scheduling with fixed jobs. 675-684 - Jeff Edmonds, Kirk Pruhs:
Scalably scheduling processes with arbitrary speedup curves. 685-692 - Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs:
Speed scaling with an arbitrary power function. 693-701 - Nikhil Bansal, Zachary Friggstad, Rohit Khandekar, Mohammad R. Salavatipour:
A logarithmic approximation for unsplittable flow on line graphs. 702-709 - Constantinos Daskalakis, Grant Schoenebeck
On the complexity of Nash equilibria of action-graph games. 710-719 - Elad Hazan, Robert Krauthgamer:
How hard is it to approximate the best Nash equilibrium? 720-727 - Maria-Florina Balcan, Avrim Blum, Yishay Mansour:
Improved equilibria via public service advertising. 728-737 - Baharak Rastegari
Stepwise randomized combinatorial auctions achieve revenue monotonicity. 738-747 - Umang Bhaskar, Lisa Fleischer, Darrell Hoy, Chien-Chung Huang:
Equilibria of atomic flow games are not unique. 748-757 - Mordecai J. Golin
A generic top-down dynamic-programming approach to prefix-free coding. 758-767 - Paolo Ferragina, Igor Nitto, Rossano Venturini:
On the bit-complexity of Lempel-Ziv compression. 768-777 - Raphaël Clifford, Klim Efremenko, Ely Porat, Amir Rothschild:
From coding theory to efficient pattern matching. 778-784 - Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, Sebastiano Vigna:
Monotone minimal perfect hashing: searching a sorted table with O(1) accesses. 785-794 - Martin Dietzfelbinger, Ulf Schellbach:
On risks of using cuckoo hashing with simple universal hash classes. 795-804 - MohammadHossein Bateni, MohammadTaghi Hajiaghayi:
Assignment problem in content distribution networks: unsplittable hard-capacitated facility location. 805-814 - Ioannis Caragiannis:
Efficient coordination mechanisms for unrelated machine scheduling. 815-824 - Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh:
Clique-width: on the price of generality. 825-834 - Benjamin Aminof, Orna Kupferman, Robby Lampert:
Reasoning about online algorithms with weighted automata. 835-844 - Mehmet A. Begen
Appointment scheduling with discrete random durations. 845-854 - Jirí Matousek, Martin Tancer, Uli Wagner
Hardness of embedding simplicial complexes in Rd. 855-864 - Alexandr Andoni, Piotr Indyk, Robert Krauthgamer:
Overcoming the l1 non-embeddability barrier: algorithms for product metrics. 865-874 - Ittai Abraham, Yair Bartal, Ofer Neiman:
On low dimensional local embeddings. 875-884 - William B. Johnson, Assaf Naor:
The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite. 885-891 - Parinya Chalermsook, Julia Chuzhoy:
Maximum independent set of rectangles. 892-901 - Dániel Marx:
Approximating fractional hypertree width. 902-911 - Zeev Nutov:
An almost O(log k)-approximation for k-connected subgraphs. 912-921 - Moran Feldman
Improved approximating algorithms for Directed Steiner Forest. 922-931 - Arnab Bhattacharyya, Elena Grigorescu
Transitive-closure spanners. 932-941 - Robert Krauthgamer, Joseph Naor, Roy Schwartz:
Partitioning graphs into balanced components. 942-949 - Raphael Yuster:
Efficient algorithms on sets of permutations, dominance, and real-weighted APSP. 950-957 - Omid Madani, Mikkel Thorup, Uri Zwick:
Discounted deterministic Markov decision processes and discounted all-pairs shortest paths. 958-967 - Christos Boutsidis, Michael W. Mahoney, Petros Drineas
An improved approximation algorithm for the column subset selection problem. 968-977 - Joel A. Tropp:
Column subset selection, matrix factorization, and eigenvalue optimization. 978-986 - Aaron Williams:
Loopless generation of multiset permutations using a constant number of variables by prefix shifts. 987-996 - Yuval Peres:
The unreasonable effectiveness of martingales. 997-1000 - Siu-Wing Cheng, Man-Kwun Chiu:
Dimension detection via slivers. 1001-1010 - David Cohen-Steiner, Herbert Edelsbrunner, John Harer, Dmitriy Morozov:
Persistent homology for kernels, images, and cokernels. 1011-1020 - Frédéric Chazal, Leonidas J. Guibas, Steve Oudot, Primoz Skraba:
Analysis of scalar fields over point cloud data. 1021-1030 - Mikhail Belkin, Jian Sun, Yusu Wang:
Constructing Laplace operator from point clouds in Rd. 1031-1040 - Benoît Hudson, Gary L. Miller, Todd Phillips, Don Sheehy
Size complexity of volume meshes vs. surface meshes. 1041-1047 - Siddharth Barman, Shuchi Chawla:
Packing multiway cuts in capacitated graphs. 1048-1057 - Ioannis Caragiannis, Jason A. Covey, Michal Feldman, Christopher M. Homan, Christos Kaklamanis, Nikos Karanikolas
On the approximability of Dodgson and Young elections. 1058-1067 - Maria-Florina Balcan, Avrim Blum, Anupam Gupta:
Approximate clustering without the approximation. 1068-1077 - S. Charles Brubaker:
Robust PCA and clustering in noisy mixtures. 1078-1087 - Marcel R. Ackermann, Johannes Blömer:
Coresets and approximate clustering for Bregman divergences. 1088-1097 - Ke Yi, Qin Zhang
Multi-dimensional online tracking. 1098-1107 - Michael A. Bender, Jeremy T. Fineman, Seth Gilbert
A new approach to incremental topological ordering. 1108-1115 - Chandra Chekuri, Benjamin Moseley:
Online scheduling to minimize the maximum delay factor. 1116-1125 - Marcin Bienkowski, Marek Chrobak, Christoph Dürr, Mathilde Hurand, Artur Jez, Lukasz Jez, Grzegorz Stachowiak:
Collecting weighted items from a dynamic queue. 1126-1135 - Spyros Angelopoulos, Pascal Schweitzer
Paging and list update under bijective analysis. 1136-1145 - Yusuke Kobayashi, Ken-ichi Kawarabayashi:
Algorithms for finding an induced cycle in planar graphs and bounded genus graphs. 1146-1155 - Ken-ichi Kawarabayashi, Bojan Mohar:
List-color-critical graphs on a fixed surface. 1156-1165 - Ken-ichi Kawarabayashi, Erik D. Demaine, MohammadTaghi Hajiaghayi:
Additive approximation algorithms for list-coloring minor-closed class of graphs. 1166-1175 - Zdenek Dvorák, Ken-ichi Kawarabayashi, Robin Thomas:
Three-coloring triangle-free planar graphs in linear time. 1176-1182 - Ken-ichi Kawarabayashi, Bruce A. Reed:
A nearly linear time algorithm for the half integral parity disjoint paths packing problem. 1183-1192 - Boaz Barak, Moritz Hardt, Satyen Kale:
The uniform hardcore lemma via approximate Bregman projections. 1193-1200 - Anthony Man-Cho So:
Improved approximation bound for quadratic optimization problems with orthogonality constraints. 1201-1209 - Khaled M. Elbassioni
On the approximability of the maximum feasible subsystem problem with 0/1-coefficients. 1210-1219 - Amitabh Basu
On the relative strength of split, triangle and quadrilateral cuts. 1220-1229 - Satoru Iwata, James B. Orlin:
A simple combinatorial algorithm for submodular function minimization. 1230-1237 - Nikhil Bansal, Ho-Leung Chan:
Weighted flow time does not admit O(1)-competitive algorithms. 1238-1244 - Moshe Babaioff, Michael Dinitz
Secretary problems: weights and discounts. 1245-1254 - Edith Cohen, Nick G. Duffield, Haim Kaplan, Carsten Lund, Mikkel Thorup:
Stream sampling for variance-optimal estimation of subset sums. 1255-1264 - Florin Constantin, Jon Feldman, S. Muthukrishnan, Martin Pál:
An online mechanism for ad slot reservations with cancellations. 1265-1274 - Anirban Dasgupta, Arpita Ghosh, Hamid Nazerzadeh, Prabhakar Raghavan:
Online story scheduling in web advertising. 1275-1284
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-07-19 02:19 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: