20. SODA 2009: New York, NY, USA
Claire Mathieu (Ed.): Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009. SIAM 2009- Gabriel Nivasch: Improved bounds and new techniques for Davenport--Schinzel sequences and their generalizations. 1-10
- Ashish Goel, Michael Kapralov, Sanjeev Khanna: 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, Peng Shi: Approximation algorithms for restless bandit problems. 28-37
- 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
- Stéphan Thomassé: A quadratic kernel for feedback vertex set. 115-119
- 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, Darren Strash: Linear-time algorithms for geometric graphs with sublinearly many crossings. 150-159
- Krishnendu Chatterjee, Luca de Alfaro, Thomas A. Henzinger: Termination criteria for solving concurrent safety and reachability games. 197-206
- Brendan Nagle, Annika Poerschke, Vojtech Rödl, Mathias Schacht: Hypergraph regularity and quasi-randomness. 227-235
- Philip N. Klein, Shay Mozes, Oren Weimann: Shortest paths in directed planar graphs with negative lengths: a linear-space O(n log2 n)-time algorithm. 236-245
- David R. Karger, Debmalya Panigrahi: A near-linear time algorithm for constructing a cactus representation of minimum cuts. 246-255
- Omid Amini, Louis Esperet, Jan van den Heuvel: 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
- Yury Lifshits, Shengyu Zhang: Combinatorial algorithms for nearest neighbors, near-duplicates and small-world design. 318-326
- Toniann Pitassi, Nathan Segerlind: Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures. 355-364
- Markus Chimani, Carsten Gutwenger, Petra Mutzel, Christian Wolf: 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 Riesenfeld, Elad Verbin: Sorting and selection in posets. 392-401
- 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
- Amin Coja-Oghlan, Uriel Feige, Alan M. Frieze, Michael Krivelevich, Dan Vilenchik: On smoothed k-CNF formulas and the Walksat algorithm. 451-460
- Amr Elmasry: Pairing heaps with O(log log n) decrease cost. 471-476
- Erik D. Demaine, Dion Harmon, John Iacono, Daniel M. Kane, Mihai Patrascu: The geometry of binary search trees. 496-505
- 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
- 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, Anil Maheshwari, Pat Morin: 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
- Nikhil Bansal, Zachary Friggstad, Rohit Khandekar, Mohammad R. Salavatipour: A logarithmic approximation for unsplittable flow on line graphs. 702-709
- Constantinos Daskalakis, Grant Schoenebeck, Gregory Valiant, Paul Valiant: On the complexity of Nash equilibria of action-graph games. 710-719
- Maria-Florina Balcan, Avrim Blum, Yishay Mansour: Improved equilibria via public service advertising. 728-737
- Baharak Rastegari, Anne Condon, Kevin Leyton-Brown: 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, Xiaoming Xu, Jiajin Yu: 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
- Alexandr Andoni, Piotr Indyk, Robert Krauthgamer: Overcoming the l1 non-embeddability barrier: algorithms for product metrics. 865-874
- William B. Johnson, Assaf Naor: The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite. 885-891
- 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, Guy Kortsarz, Zeev Nutov: Improved approximating algorithms for Directed Steiner Forest. 922-931
- Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff: 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
- 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
- Ioannis Caragiannis, Jason A. Covey, Michal Feldman, Christopher M. Homan, Christos Kaklamanis, Nikos Karanikolas, Ariel D. Procaccia, Jeffrey S. Rosenschein: 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
- 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
- Yusuke Kobayashi, Ken-ichi Kawarabayashi: Algorithms for finding an induced cycle in planar graphs and bounded genus graphs. 1146-1155
- Ken-ichi Kawarabayashi, Erik D. Demaine, MohammadTaghi Hajiaghayi: Additive approximation algorithms for list-coloring minor-closed class of graphs. 1166-1175
- Zdenek Dvorak, 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, Rajiv Raman, Saurabh Ray, René Sitters: On the approximability of the maximum feasible subsystem problem with 0/1-coefficients. 1210-1219
- Amitabh Basu, Pierre Bonami, Gérard Cornuéjols, François Margot: 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, Anupam Gupta, Nicole Immorlica, Kunal Talwar: 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
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-18T214307 by the dblp team