default search action
17th SODA 2006: Miami, Florida, USA
- Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22-26, 2006. ACM Press 2006, ISBN 0-89871-605-5
- 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(20.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 S. 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 - T.-H. Hubert 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
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
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 C. 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 L1 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 Ramaswami 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 L1. 1010-1017 - Moses Charikar, Mohammad Taghi Hajiaghayi, Howard J. Karloff, Satish Rao:
l22 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
Matrix approximation and projective clustering via volume sampling. 1117-1126 - Petros Drineas
Sampling algorithms for l2 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
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 2024-12-19 22:18 CET 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: