17. SODA 2006: Miami, Florida, USA

• Virginia Vassilevska, Ryan Williams, Shan Leung Maverick Woo:
  Confronting hardness using a hybrid approach. 1-10
  
• Arist Kojevnikov, Alexander S. Kulikov:
  A new approach to proving upper bounds for MAX-2-SAT. 11-17
  
• Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch:
  Measure and conquer: a simple O(2^0.288n) independent set algorithm. 18-25
  
• Vadim V. Lozin, Martin Milanic:
  A polynomial algorithm to find an independent set of maximum weight in a fork-free graph. 26-30
  
• Wolfgang W. Bein, Mordecai J. Golin, Lawrence L. Larmore, Yan Zhang:
  The Knuth-Yao quadrangle-inequality speedup is a consequence of total-monotonicity. 31-40
  
• Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh Vempala:
  Local versus global properties of metric spaces. 41-50
  
• Moses Charikar, Konstantin Makarychev, Yury Makarychev:
  Directed metrics and directed graph partitioning problems. 51-60
  
• Kedar Dhamdhere, Anupam Gupta, Harald Räcke:
  Improved embeddings of graph metrics into random trees. 61-69
  
• Hubert T.-H. Chan, Anupam Gupta:
  Small hop-diameter sparse spanners for doubling metrics. 70-78
  
• Manor Mendel, Assaf Naor:
  Metric cotype. 79-88
  
• Susanne Albers, Stefan Eilts, Eyal Even-Dar, Yishay Mansour, Liam Roditty:
  On nash equilibria for a network creation game. 89-98
  
• Anupam Gupta, Kunal Talwar:
  Approximating unique games. 99-106
  
• Peter Bro Miltersen, Troels Bjerre Sørensen:
  Computing sequential equilibria for two-player games. 107-116
  
• Marcin Jurdzinski, Mike Paterson, Uri Zwick:
  A deterministic subexponential algorithm for solving parity games. 117-123
  
• Xiaotie Deng, Qizhi Fang, Xiaoxun Sun:
  Finding nucleolus of flow game. 124-131
  
• Rakesh V. Vohra:
  Predicting the "unpredictable". 132
  
• Sven Koenig, Apurva Mudgal, Craig A. Tovey:
  A near-tight approximation lower bound and algorithm for the kidnapped robot problem. 133-142
  
• Klaus Jansen, Roberto Solis-Oba:
  An asymptotic approximation algorithm for 3D-strip packing. 143-152
  
• Zoya Svitkina, Éva Tardos:
  Facility location with hierarchical facility costs. 153-161
  
• Erik D. Demaine, Mohammad Taghi Hajiaghayi, Uriel Feige, Mohammad R. Salavatipour:
  Combination can be hard: approximability of the unique coverage problem. 162-171
  
• Ernst Althaus, Rouven Naujoks:
  Computing steiner minimum trees in Hamming metric. 172-181
  
• Pankaj K. Agarwal, Sariel Har-Peled, Hai Yu:
  Robust shape fitting via peeling and grating coresets. 182-191
  
• Éric Colin de Verdière, Jeff Erickson:
  Tightening non-simple paths and cycles on surfaces. 192-201
  
• Siu-Wing Cheng, Tamal K. Dey, Edgar A. Ramos, Rephael Wenger:
  Anisotropic surface meshing. 202-211
  
• Prosenjit Bose, Jurek Czyzowicz, Zhicheng Gao, Pat Morin, David R. Wood:
  Simultaneous diagonal flips in plane triangulations. 212-221
  
• Anna Lubiw, Mark Petrick, Michael J. Spriggs:
  Morphing orthogonal planar graph drawings. 222-230
  
• Mike Paterson, Uri Zwick:
  Overhang. 231-240
  
• Micah Adler, Nicholas J. A. Harvey, Kamal Jain, Robert D. Kleinberg, April Rasala Lehman:
  On the capacity of information networks. 241-250
  
• Micah Adler, Erik D. Demaine, Nicholas J. A. Harvey, Mihai Patrascu:
  Lower bounds for asymmetric communication channels and distributed source coding. 251-260
  
• Nir Ailon, Bernard Chazelle, Seshadhri Comandur, Ding Liu:
  Self-improving algorithms. 261-270
  
• Jeff Edmonds, Kirk Pruhs:
  Cake cutting really is not a piece of cake. 271-278
  
• Noga Alon, Tali Kaufman, Michael Krivelevich, Dana Ron:
  Testing triangle-freeness in general graphs. 279-288
  
• Martin Grohe, Dániel Marx:
  Constraint solving via fractional edge covers. 289-298
  
• Eldar Fischer, Arie Matsliah:
  Testing graph isomorphism. 299-308
  
• Min Chih Lin, Jayme Luiz Szwarcfiter:
  Efficient construction of unit circular-arc models. 309-315
  
• Shakhar Smorodinsky:
  On the chromatic number of some geometric hypergraphs. 316-323
  
• Moses Charikar, Samir Khuller:
  A robust maximum completion time measure for scheduling. 324-333
  
• Ho-Leung Chan, Tak Wah Lam, Kin-Shing Liu:
  Extra unit-speed machines are almost as powerful as speedy machines for competitive flow time scheduling. 334-343
  
• Nikhil Bansal, Don Coppersmith, Maxim Sviridenko:
  Improved approximation algorithms for broadcast scheduling. 344-353
  
• Petra Berenbrink, Tom Friedetzky, Leslie Ann Goldberg, Paul W. Goldberg, Zengjian Hu, Russell A. Martin:
  Distributed selfish load balancing. 354-363
  
• Philippe Baptiste:
  Scheduling unit tasks to minimize the number of idle periods: a polynomial time algorithm for offline dynamic power management. 364-367
  
• Alexander Golynski, J. Ian Munro, S. Srinivasa Rao:
  Rank/select operations on large alphabets: a tool for text indexing. 368-373
  
• Chengwen Chris Wang, Jonathan Derryberry, Daniel Dominic Sleator:
  O(log log n)-competitive dynamic binary search trees. 374-383
  
• Michael T. Goodrich, Michael J. Nelson, Jonathan Z. Sun:
  The rainbow skip graph: a fault-tolerant constant-degree distributed data structure. 384-393
  
• Loukas Georgiadis, Robert Endre Tarjan, Renato Fonseca F. Werneck:
  Design of data structures for mergeable trees. 394-403
  
• Gianni Franceschini, J. Ian Munro:
  Implicit dictionaries with O(1) modifications per update and fast search. 404-413
  
• Ivona Bezáková, Nayantara Bhatnagar, Eric Vigoda:
  Sampling binary contingency tables with a greedy start. 414-423
  
• Philipp Woelfel:
  Asymmetric balanced allocation with simple hash functions. 424-433
  
• Krishnaram Kenthapadi, Rina Panigrahy:
  Balanced allocation on graphs. 434-443
  
• Ming Li, Bin Ma, Louxin Zhang:
  Superiority and complexity of the spaced seeds. 444-453
  
• Michael Krivelevich, Dan Vilenchik:
  Solving random satisfiable 3CNF formulas in expected polynomial time. 454-463
  
• Jie Gao, Michael Langberg, Leonard J. Schulman:
  Analysis of incomplete data and an intrinsic-dimension Helly theorem. 464-473
  
• Olaf A. Hall-Holt, Matthew J. Katz, Piyush Kumar, Joseph S. B. Mitchell, Arik Sityon:
  Finding large sticks and potatoes in polygons. 474-483
  
• Haim Kaplan, Micha Sharir:
  Randomized incremental constructions of three-dimensional convex hulls and planar voronoi diagrams, and approximate range counting. 484-493
  
• Mark de Berg, Chris Gray:
  Vertical ray shooting and computing depth orders for fat objects. 494-503
  
• Oswin Aichholzer, Thomas Hackl, Birgit Vogtenhuber, Clemens Huemer, Ferran Hurtado, Hannes Krasser:
  On the number of plane graphs. 504-513
  
• Timothy M. Chan:
  All-pairs shortest paths for unweighted undirected graphs in o(mn) time. 514-523
  
• Glencora Borradaile, Philip N. Klein:
  An O (n log n) algorithm for maximum st-flow in a directed planar graph. 524-533
  
• Mateo Restrepo, David P. Williamson:
  A simple GAP-canceling algorithm for the generalized maximum flow problem. 534-543
  
• Vladimir G. Deineko, Bettina Klinz, Gerhard J. Woeginger:
  Four point conditions and exponential neighborhoods for symmetric TSP. 544-553
  
• Harold N. Gabow:
  Upper degree-constrained partial orientations. 554-563
  
• Kamalika Chaudhuri, Kevin Chen, Radu Mihaescu, Satish Rao:
  On the tandem duplication-random loss model of genome rearrangement. 564-570
  
• Ming-Yang Kao, Robert T. Schweller:
  Reducing tile complexity for self-assembly through temperature programming. 571-580
  
• Gerth Stølting Brodal, Rolf Fagerberg:
  Cache-oblivious string dictionaries. 581-590
  
• Rezaul Alam Chowdhury, Vijaya Ramachandran:
  Cache-oblivious dynamic programming. 591-600
  
• Deepak Ajwani, Roman Dementiev, Ulrich Meyer:
  A computational study of external-memory BFS algorithms. 601-610
  
• Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni, Maxim Sviridenko:
  Tight approximation algorithms for maximum general assignment problems. 611-620
  
• Daniel Golovin, Viswanath Nagarajan, Mohit Singh:
  Approximating the k-multicut problem. 621-630
  
• Mohammad Taghi Hajiaghayi, Kamal Jain:
  The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema. 631-640
  
• Piotr Berman, Marek Karpinski:
  8/7-approximation algorithm for (1, 2)-TSP. 641-648
  
• Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Frank Thomson Leighton:
  Improved lower and upper bounds for universal TSP in planar metrics. 649-658
  
• Bruno Codenotti, Amin Saberi, Kasturi R. Varadarajan, Yinyu Ye:
  Leontief economies encode nonzero sum two-player games. 659-667
  
• Richard Cole, Yevgeniy Dodis, Tim Roughgarden:
  Bottleneck links, variable demand, and the tragedy of the commons. 668-677
  
• Krishnendu Chatterjee, Luca de Alfaro, Thomas A. Henzinger:
  The complexity of quantitative concurrent parity games. 678-687
  
• Kamal Jain, Kasturi R. Varadarajan:
  Equilibria for economies with production: constant-returns technologies and production planning constraints. 688-697
  
• Sudipto Guha, Boulos Harb:
  Approximation algorithms for wavelet transform coding of data streams. 698-707
  
• Lakshminath Bhuvanagiri, Sumit Ganguly, Deepanjan Kesh, Chandan Saha:
  Simpler algorithm for estimating frequency moments of data streams. 708-713
  
• Camil Demetrescu, Irene Finocchi, Andrea Ribichini:
  Trading off space for passes in graph streaming problems. 714-723
  
• Lap-Kei Lee, H. F. Ting:
  Maintaining significant stream statistics over sliding windows. 724-732
  
• Sudipto Guha, Andrew McGregor, Suresh Venkatasubramanian:
  Streaming and sublinear approximation of entropy and information distances. 733-742
  
• Jesús A. De Loera, Raymond Hemmecke, Matthias Köppe, Robert Weismantel:
  FPTAS for mixed-integer polynomial optimization with a fixed number of variables. 743-748
  
• Bernd Gärtner, Ingo Schurr:
  Linear programming and unique sink orientations. 749-757
  
• Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled M. Elbassioni, Vladimir Gurvich:
  Generating all vertices of a polyhedron is hard. 758-765
  
• Anthony Man-Cho So, Yinyu Ye:
  A semidefinite programming approach to tensegrity theory and realizability of graphs. 766-775
  
• Don Coppersmith, Lisa Fleischer, Atri Rudra:
  Ordering by weighted number of wins gives a good ranking for weighted tournaments. 776-782
  
• Stanislav Angelov, Boulos Harb, Sampath Kannan, Li-San Wang:
  Weighted isotonic regression under the L₁ norm. 783-791
  
• Tugkan Batu, Funda Ergün, Süleyman Cenk Sahinalp:
  Oblivious string embeddings and edit distance approximations. 792-801
  
• Mikkel Thorup, Uri Zwick:
  Spanners and emulators with sublinear distance errors. 802-809
  
• Sang-il Oum, Paul D. Seymour:
  Certifying large branch-width. 810-813
  
• Jan Obdrzálek:
  DAG-width: connectivity measure for directed graphs. 814-821
  
• László Babai:
  On the diameter of Eulerian orientations of graphs. 822-831
  
• Michael Kaufmann, Jan Kratochvíl, Katharina Anna Lehmann, Amarendran R. Subramanian:
  Max-tolerance graphs as intersection graphs: cliques, cycles, and recognition. 832-841
  
• Ephraim Korach, Thành Nguyen, Britta Peis:
  Subgraph characterization of Red/Blue-Split Graph and König Egerváry Graphs. 842-850
  
• Daniela Kühn, Deryk Osthus:
  Critical chromatic number and the complexity of perfect packings in graphs. 851-859
  
• Micha Sharir, Emo Welzl:
  On the number of crossing-free matchings, (cycles, and partitions). 860-869
  
• Dana Randall:
  Slow mixing of glauber dynamics via topological obstructions. 870-879
  
• Harry Buhrman, Robert Spalek:
  Quantum verification of matrix products. 880-889
  
• Antar Bandyopadhyay, David Gamarnik:
  Counting without sampling: new algorithms for enumeration problems using statistical physics. 890-899
  
• Ivona Bezáková, Daniel Stefankovic, Vijay V. Vazirani, Eric Vigoda:
  Accelerating simulated annealing for the permanent and combinatorial counting problems. 900-907
  
• Parikshit Gopalan:
  Query-efficient algorithms for polynomial interpolation over composites. 908-917
  
• Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Frank Thomson Leighton, Harald Räcke:
  New lower bounds for oblivious routing in undirected graphs. 918-927
  
• Robert D. Kleinberg:
  Anytime algorithms for multi-armed bandit problems. 928-936
  
• Varsha Dani, Thomas P. Hayes:
  Robbing the bandit: less regret in online geometric optimization against an adaptive adversary. 937-943
  
• Ferdinando Cicalese, Eduardo Sany Laber:
  On the competitive ratio of evaluating priced functions. 944-953
  
• Adam Meyerson, Akash Nanavati, Laura J. Poplawski:
  Randomized online algorithms for minimum metric bipartite matching. 954-959
  
• Alan M. Frieze:
  Random graphs. 960
  
• David Arthur, Rina Panigrahy:
  Analyzing BitTorrent and related peer-to-peer networks. 961-969
  
• Anupam Gupta, Mohammad Taghi Hajiaghayi, Harald Räcke:
  Oblivious network design. 970-979
  
• Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer:
  The price of being near-sighted. 980-989
  
• Valerie King, Jared Saia, Vishal Sanwalani, Erik Vee:
  Scalable leader election. 990-999
  
• Alexander Kröller, Sándor P. Fekete, Dennis Pfisterer, Stefan Fischer:
  Deterministic boundary recognition and topology extraction for large sensor networks. 1000-1009
  
• Robert Krauthgamer, Yuval Rabani:
  Improved lower bounds for embeddings into L₁. 1010-1017
  
• Moses Charikar, Mohammad Taghi Hajiaghayi, Howard J. Karloff, Satish Rao:
  l²₂ spreading metrics for vertex ordering problems. 1018-1027
  
• James R. Lee, Assaf Naor, Yuval Peres:
  Trees and Markov convexity. 1028-1037
  
• Domingos Dellamonica Jr., Yoshiharu Kohayakawa:
  An algorithmic Friedman--Pippenger theorem on tree embeddings and applications to routing. 1038-1044
  
• Yuval Emek, David Peleg:
  A tight upper bound on the probabilistic embedding of series-parallel graphs. 1045-1053
  
• Moshe Babaioff, Ron Lavi, Elan Pavlov:
  Single-value combinatorial auctions and implementation in undominated strategies. 1054-1063
  
• Shahar Dobzinski, Michael Schapira:
  An improved approximation algorithm for combinatorial auctions with submodular bidders. 1064-1073
  
• Zoë Abrams:
  Revenue maximization when bidders have budgets. 1074-1082
  
• Gagan Aggarwal, Jason D. Hartline:
  Knapsack auctions. 1083-1092
  
• Patrick Briest, Piotr Krysta:
  Single-minded unlimited supply pricing on sparse instances. 1093-1102
  
• Nicholas J. A. Harvey, David R. Karger, Sergey Yekhanin:
  The complexity of matrix completion. 1103-1111
  
• Steven Butler:
  Relating singular values and discrepancy of weighted directed graphs. 1112-1116
  
• Amit Deshpande, Luis Rademacher, Santosh Vempala, Grant Wang:
  Matrix approximation and projective clustering via volume sampling. 1117-1126
  
• Petros Drineas, Michael W. Mahoney, S. Muthukrishnan:
  Sampling algorithms for l₂ regression and applications. 1127-1136
  
• Deepak Agarwal, Jeff M. Phillips, Suresh Venkatasubramanian:
  The hunting of the bump: on maximizing statistical discrepancy. 1137-1146
  
• Guolong Lin, Chandrashekhar Nagarajan, Rajmohan Rajaraman, David P. Williamson:
  A general approach for incremental approximation and hierarchical clustering. 1147-1156
  
• Kevin L. Chang, Ravi Kannan:
  The space complexity of pass-efficient algorithms for clustering. 1157-1166
  
• Ioannis Giotis, Venkatesan Guruswami:
  Correlation clustering with a fixed number of clusters. 1167-1176
  
• Ke Chen:
  On k-Median clustering in high dimensions. 1177-1185
  
• Rina Panigrahy:
  Entropy based nearest neighbor search in high dimensions. 1186-1195
  
• Timothy M. Chan:
  A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries. 1196-1202
  
• Alexandr Andoni, Piotr Indyk:
  Efficient algorithms for substring near neighbor problem. 1203-1212
  
• Sergio Cabello:
  Many distances in planar graphs. 1213-1220
  
• Amihood Amir, Yonatan Aumann, Gary Benson, Avivit Levy, Ohad Lipsky, Ely Porat, Steven Skiena, Uzi Vishne:
  Pattern matching with address errors: rearrangement distances. 1221-1229
  
• Kunihiko Sadakane, Roberto Grossi:
  Squeezing succinct data structures into entropy bounds. 1230-1239
  

Last update Wed May 22 16:38:59 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page