20. SODA 2009: New York, NY, USA

• 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
  
• 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 Dvorak, 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, Darren Strash:
  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 R³. 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, Mathias Schacht:
  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, Oren Weimann:
  Shortest paths in directed planar graphs with negative lengths: a linear-space O(n log² 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
  
• 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, 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
  
• 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, 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
  
• 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 M. 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, Santosh Vempala:
  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, 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
  
• 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, Gregory Valiant, Paul Valiant:
  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, 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
  
• Mehmet A. Begen, Maurice Queyranne:
  Appointment scheduling with discrete random durations. 845-854
  
• Jirí Matousek, Martin Tancer, Uli Wagner:
  Hardness of embedding simplicial complexes in R^d. 855-864
  
• Alexandr Andoni, Piotr Indyk, Robert Krauthgamer:
  Overcoming the l₁ 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, 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
  
• 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 R^d. 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, 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
  
• 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 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
  

Last update Tue May 21 18:04:44 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page