default search action
22nd SODA 2011: San Francisco, California, USA
- Dana Randall:
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011. SIAM 2011, ISBN 978-0-89871-993-2
Session 1A
- T. S. Jayram, David P. Woodruff:
Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Sub-Constant Error. 1-10 - Elad Verbin, Wei Yu:
The Streaming Complexity of Cycle Counting, Sorting by Reversals, and Other Problems. 11-25 - Vladimir Braverman, Adam Meyerson, Rafail Ostrovsky, Alan Roytman, Michael Shindler, Brian Tagiku:
Streaming k-means on Well-Clusterable Data. 26-40 - Eric Price:
Efficient Sketches for the Set Query Problem. 41-56 - Guy Feigenblat, Ely Porat, Ariel Shiftan:
Exponential Time Improvement for min-wise Based Algorithms. 57-66
Session 1B
- Gautier Stauffer, Guillaume Massonnet, Christophe Rapine, Jean-Philippe Gayon:
A simple and fast 2-approximation algorithms for the one-warehouse multi-retailers problem. 67-79 - Jian Li, Samir Khuller:
Generalized Machine Activation Problems. 80-94 - Sungjin Im, Benjamin Moseley:
Online Scalable Algorithm for Minimizing ℓk-norms of Weighted Flow Time On Unrelated Machines. 95-108 - Jeff Edmonds, Sungjin Im, Benjamin Moseley:
Online Scalable Scheduling for the ℓk-norms of Flow Time Without Conservation of Work. 109-119 - Kyle Fox, Benjamin Moseley:
Online Scheduling on Identical Machines using SRPT. 120-128
Session 1C
- Jennifer Debroni, John D. Eblen, Michael A. Langston, Wendy J. Myrvold
, Peter W. Shor, Dinesh Weerapurage:
A complete resolution of the Keller maximum clique problem. 129-135 - Amin Coja-Oghlan, Charilaos Efthymiou:
On independent sets in random graphs. 136-144 - Torsten Mütze, Thomas Rast, Reto Spöhel:
Coloring random graphs online without creating monochromatic subgraphs. 145-158 - Yoshiharu Kohayakawa, Sangjune Lee, Vojtech Rödl:
The maximum size of a Sidon set contained in a sparse random set of integers. 159-171 - Philippe Flajolet, Maryse Pelletier, Michèle Soria:
On Buffon Machines and Numbers. 172-183
Session 2
- Bruce A. Reed:
Graph Coloring via The Probabilistic Method. 184
Best Paper Presentation
- Nir Ailon, Edo Liberty:
An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform. 185-191
Session 3A
- Umang Bhaskar, Lisa Fleischer, Elliot Anshelevich
A Stackelberg Strategy for Routing Flow over Time. 192-201 - Oliver Friedmann, Thomas Dueholm Hansen, Uri Zwick:
A subexponential lower bound for the Random Facet algorithm for Parity Games. 202-216 - Yang Cai
On Minmax Theorems for Multiplayer Games. 217-234 - Constantinos Daskalakis, Alan Deckelbaum, Anthony Kim
Near-Optimal No-Regret Algorithms for Zero-Sum Games. 235-254 - Tim Roughgarden, Florian Schoppmann:
Local Smoothness and the Price of Anarchy in Atomic Splittable Congestion Games. 255-267
Session 3B
- Pankaj K. Agarwal, Thomas Mølhave, Bardia Sadri:
I/O-Efficient Contour Queries on Terrains. 268-284 - Mark de Berg, Herman J. Haverkort, Constantinos P. Tsirogiannis:
Implicit Flow Routing on Terrains with Applications to Surface Networks and Drainage Structures. 285-296 - Jeff Erickson, Amir Nayyeri:
Shortest Non-Crossing Walks in the Plane. 297-208 - Danny Z. Chen, Haitao Wang:
Computing Shortest Paths amid Pseudodisks. 309-226 - Luca Foschini, John Hershberger, Subhash Suri:
On the Complexity of Time-Dependent Shortest Paths. 327-341
Session 3C
- Michael Drmota, Wojciech Szpankowski:
A Master Theorem for Discrete Divide and Conquer Recurrences. 342-361 - Pawel Gawrychowski:
Optimal pattern matching in LZW compressed strings. 362-372 - Philip Bille, Gad M. Landau, Rajeev Raman, Kunihiko Sadakane, Srinivasa Rao Satti
Random Access to grammar-Compressed Strings. 373-389 - Peyman Afshani, Gerth Stølting Brodal, Norbert Zeh:
Ordered and Unordered Top-K Range Reporting in Large Data Sets. 390-400 - Marek Karpinski, Yakov Nekrich
Top-K Color Queries for Document Retrieval. 401-411
Session 4A
- Yuval Peres, Alistair Sinclair, Perla Sousi, Alexandre Stauffer:
Mobile Geometric Graphs: Detection, Coverage and Percolation. 412-428 - Petra Berenbrink, Colin Cooper, Tom Friedetzky
Randomized Diffusion for Indivisible Loads. 429-439 - Keren Censor-Hillel, Hadas Shachnai:
Fast Information Spreading in Graphs with Large Weak Conductance. 440-448 - George Giakkoupis, Philipp Woelfel:
On the Randomness Requirements of Rumor Spreading. 449-461 - Thomas Sauerwald, Alexandre Stauffer:
Rumor Spreading and Vertex Expansion on Regular Graphs. 462-475
Session 4B
- Friedrich Eisenbrand, Dömötör Pálvölgyi, Thomas Rothvoß:
Bin Packing via Discrepancy of Permutations. 476-481 - Amit Deshpande, Madhur Tulsiani, Nisheeth K. Vishnoi:
Algorithms and Hardness for Subspace Approximation. 482-496 - Aditya Bhaskara, Aravindan Vijayaraghavan:
Approximating Matrix p-norms. 497-511 - Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer
Subsampling Mathematical Relaxations and Average-case Complexity. 512-531 - Lorenzo Orecchia, Nisheeth K. Vishnoi:
Towards an SDP-based Approach to Spectral Methods: A Nearly-Linear-Time Algorithm for Graph Partitioning and Decomposition. 532-545
Session 4C
- Ben Reichardt:
Faster quantum algorithm for evaluating game trees. 546-559 - Ben Reichardt:
Reflections for quantum query algorithms. 560-569 - Matthew Cook, Yunhui Fu, Robert T. Schweller:
Temperature 1 Self-Assembly: Deterministic Assembly in 3D and Probabilistic Assembly in 2D. 570-589 - Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari, Shinnosuke Seki:
The Power of Nondeterminism in Self-Assembly. 590-602 - Günter Rote, Uri Zwick
Collapse. 603-613
Session 5A
- Karthekeyan Chandrasekaran, Richard M. Karp, Erick Moreno-Centeno
Algorithms for Implicit Hitting Set Problems. 614-629 - Yuri Faenza, Gianpaolo Oriolo, Gautier Stauffer:
An algorithmic decomposition of claw-free graphs leading to an O(n3)-algorithm for the weighted stable set problem. 630-646 - Kevin P. Costello
Randomized greedy: new variants of some classic approximation algorithms. 647-655 - Matthias Poloczek, Georg Schnitger:
Randomized Variants of Johnson's Algorithm for MAX SAT. 656-663 - Heidi Gebauer, Tibor Szabó, Gábor Tardos:
The Local Lemma is Tight for SAT. 664-674
Session 5B
- Fabrizio Grandoni
Pricing on Paths: A PTAS for the Highway Problem. 675-684 - Ning Chen, Nick Gravin, Pinyan Lu
On the Approximability of Budget Feasible Mechanisms. 685-699 - Kshipra Bhawalkar, Tim Roughgarden:
Welfare Guarantees for Combinatorial Auctions with Item Bidding. 700-709 - Qiqi Yan:
Mechanism Design via Correlation Gap. 710-719 - Xiaohui Bei
Bayesian Incentive Compatibility via Fractional Assignments. 720-733 - Jason D. Hartline, Robert Kleinberg, Azarakhsh Malekian:
Bayesian Incentive Compatibility via Matchings. 734-747
Session 5C
- Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh:
Bidimensionality and EPTAS. 748-759 - Daniel Lokshtanov, Dániel Marx, Saket Saurabh:
Slightly Superexponential Parameterized Problems. 760-776 - Daniel Lokshtanov, Dániel Marx, Saket Saurabh:
Known Algorithms on Graphs on Bounded Treewidth are Probably Optimal. 777-789 - Constantinos Daskalakis, Christos H. Papadimitriou:
Continuous Local Search. 790-804 - Allan Grønlund Jørgensen, Kasper Green Larsen:
Range Selection and Median: Tight Cell Probe Lower Bounds and Adaptive Data Structures. 805-813
Session 6 - Invited Plenary Session
- William T. Freeman:
Where computer vision needs help from computer science. 814-819
Session 7A
- Shay Solomon:
An Optimal-Time Construction of Sparse Euclidean Spanners with Tiny Diameter. 820-839 - Yair Bartal, Lee-Ad Gottlieb, Tsvi Kopelowitz, Moshe Lewenstein, Liam Roditty:
Fast, precise and dynamic distance queries. 840-853 - Sariel Har-Peled
Approximate Nearest Neighbor Search for Low Dimensional Queries. 854-867 - Yair Bartal, Ben Recht, Leonard J. Schulman
Dimensionality reduction: Beyond the Johnson-Lindenstrauss bound. 868-887 - Lee-Ad Gottlieb, Robert Krauthgamer:
A Nonlinear Approach to Dimension Reduction. 888-899
Session 7B
- Sonny Ben-Shimon, Asaf Ferber, Dan Hefetz, Michael Krivelevich:
Hitting time results for Maker-Breaker games. 900-912 - Alan M. Frieze, Michael Krivelevich, Po-Shen Loh
Packing tight Hamilton cycles in 3-uniform hypergraphs. 913-932 - Colin Cooper, Martin E. Dyer
Networks of random cycles. 933-944 - Ricardo Restrepo, Daniel Stefankovic, Juan Carlos Vera, Eric Vigoda, Linji Yang:
Phase Transition for Glauber Dynamics for Independent Sets on Regular Trees. 945-956 - Amin Coja-Oghlan:
On Belief Propagation Guided Decimation for Random k-SAT. 957-966
Session 7C
- Shayan Oveis Gharan, Amin Saberi:
The Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus. 967-975 - Matthew Andrews, Mohammad Taghi Hajiaghayi, Howard J. Karloff, Ankur Moitra:
Capacitated Metric Labeling. 976-995 - Laura J. Poplawski, Rajmohan Rajaraman:
Multicommodity Facility Location under Group Steiner Access Cost. 996-1013 - Debmalya Panigrahi:
Survivable Network Design Problems in Wireless Networks. 1014-1027 - MohammadHossein Bateni, Chandra Chekuri, Alina Ene, Mohammad Taghi Hajiaghayi, Nitish Korula, Dániel Marx:
Prize-collecting Steiner Problems on Planar Graphs. 1028-1049
Session 8A
- Julia Chuzhoy, Yury Makarychev, Anastasios Sidiropoulos:
On Graph Crossing Number and Edge Planarization. 1050-1069 - Yossi Azar, Iftah Gamzu:
Ranking with Submodular Valuations. 1070-1079 - Chandra Chekuri, Jan Vondrák, Rico Zenklusen:
Multi-budgeted Matchings and Matroid Intersection via Dependent Rounding. 1080-1097 - Shayan Oveis Gharan, Jan Vondrák:
Submodular Maximization by Simulated Annealing. 1098-1116 - Ravishankar Krishnaswamy, Amit Kumar
The Matroid Median Problem. 1117-1130
Session 8B
- Timothy M. Chan:
Persistent Predecessor Search and Orthogonal point Location on the Word RAM. 1131-1145 - Ankan Saha, S. V. N. Vishwanathan, Xinhua Zhang:
New Approximation Algorithms for Minimum Enclosing Convex Shapes. 1146-1160 - Jacob Fox, János Pach:
Computing the Independence Number of Intersection Graphs. 1161-1165 - Jeff Erickson, Amir Nayyeri:
Minimum Cuts and Shortest Non-Separating Cycles via Homology Covers. 1166-1176 - Erik D. Demaine, André Schulz:
Embedding Stacked Polytopes on a Polynomial-Size Grid. 1177-1187
Session 8C
- Jacob Fox, Mikhail Gromov, Vincent Lafforgue, Assaf Naor, János Pach:
Overlap properties of geometric expanders. 1188-1197 - Konstantinos Panagiotou, Angelika Steger:
On the Degree Distribution of Random Planar Graphs. 1198-1210 - Colin Cooper, Alan M. Frieze:
Component structure of the vacant set induced by a random walk on a random graph. 1211-1221 - Nikolaos Fountoulakis
The Multiple-Orientability Thresholds for Random Hypergraphs. 1222-1236 - Shiva Prasad Kasiviswanathan, Cristopher Moore
The Rigidity Transition in Random Graphs. 1237-1252
Session 9A
- Gagan Aggarwal, Gagan Goel, Chinmay Karande, Aranyak Mehta:
Online Vertex-Weighted Bipartite Matching and Single-bid Budgeted Allocations. 1253-1264 - Sungjin Im, Yajun Wang:
Secretary Problems: Laminar Matroid and Interval Scheduling. 1265-1274 - José A. Soto:
Matroid Secretary Problem in the Random Assignment Model. 1275-1284 - Vahideh H. Manshadi, Shayan Oveis Gharan, Amin Saberi:
Online Stochastic Matching: Online Actions Based on Offline Statistics. 1285-1294 - Marcin Bienkowski:
An Optimal Lower Bound for Buffer Management in Multi-Queue Switches. 1295-1305
Session 9B
- George B. Mertzios:
An Intersection Model for Multitolerance Graphs: Efficient Algorithms and Hierarchy. 1306-1317 - Krishnendu Chatterjee, Monika Henzinger:
Faster and Dynamic Algorithms for Maximal End-Component Decomposition and Related Graph Problems in Probabilistic Verification. 1318-1336 - Virginia Vassilevska Williams:
Faster Replacement Paths. 1337-1346 - Jeff Erickson, Amir Nayyeri:
Computing Replacement Paths in Surface Embedded Graphs. 1347-1354 - Aaron Bernstein, Liam Roditty:
Improved Dynamic Algorithms for Maintaining Approximate Shortest Paths Under Deletions. 1355-1365
Session 9C
- Ho Yee Cheung, Lap Chi Lau, Kai Man Leung:
Algebraic Algorithms for Linear Matroid Parity Problems. 1366-1382 - Nader H. Bshouty, Hanna Mazzawi:
On Parity Check (0, 1)-Matrix over Zp. 1383-1394 - László Babai
Code Equivalence and Group Isomorphism. 1395-1408 - Neeraj Kayal:
Efficient algorithms for some special cases of the polynomial equivalence problem. 1409-1421 - Avner Magen, Anastasios Zouzias:
Low Rank Matrix-valued Chernoff Bounds and Approximate Matrix Multiplication. 1422-1436
Session 10 - Invited Plenary Session
- Timothy M. Chan:
Computational Geometry for Non-Geometers: Recent Developments on Some Classical Problems. 1437
Session 11A
- Jakub Lacki:
Improved Deterministic Algorithms for Decremental Transitive Closure and Strongly Connected Components. 1438-1445 - Liam Roditty, Roei Tov:
Approximating the Girth. 1446-1454 - Yuval Emek, Amos Korman, Yuval Shavitt
Approximating the Statistics of various Properties in Randomly Weighted Graphs. 1455-1467 - Miroslaw Kowaluk, Andrzej Lingas, Eva-Marta Lundell:
Counting and detecting small subgraphs via equations and matrix multiplication. 1468-1476 - Xin He, Huaming Zhang:
On Succinct Convex Greedy Drawing of 3-Connected Plane Graphs. 1477-1486
Session 11B
- Petra Berenbrink, Martin Hoefer, Thomas Sauerwald:
Distributed Selfish Load Balancing on Networks. 1487-1497 - Constantinos Daskalakis:
On the Complexity of Approximating a Nash Equilibrium. 1498-1517 - Yashodhan Kanoria, Mohsen Bayati, Christian Borgs
Fast Convergence of Natural Bargaining Dynamics in Exchange Networks. 1518-1537 - Magnús M. Halldórsson, Pradipta Mitra:
Wireless Capacity with Oblivious Power in General Metrics. 1538-1548 - Thomas Kesselheim:
A Constant-Factor Approximation for Wireless Capacity Maximization with Power Control in the SINR Model. 1549-1559
Session 11C
- Amit Kumar
On LP-Based Approximability for Strict CSPs. 1560-1573 - Venkatesan Guruswami, Yuan Zhou
Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set. 1574-1589 - Ilias Diakonikolas, Ryan O'Donnell, Rocco A. Servedio
Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions. 1590-1606 - Moses Charikar, Alantha Newman, Aleksandar Nikolov:
Tight Hardness Results for Minimizing Discrepancy. 1607-1614 - Venkatesan Guruswami, Ali Kemal Sinop:
The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number. 1615-1626
Session 12A
- Chaitanya Swamy:
Risk-Averse Stochastic Optimization: Probabilistically-Constrained Models and Algorithms for Black-Box Distributions. 1627-1646 - Anand Bhalgat, Ashish Goel, Sanjeev Khanna:
Improved Approximation Results for Stochastic Knapsack Problems. 1647-1665 - Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk:
The stubborn problem is stubborn no more (a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem). 1666-1674 - Gary L. Miller, Richard Peng, Russell Schwartz, Charalampos E. Tsourakakis
Approximate Dynamic Programming using Halfspace Queries and Multiscale Monge Decomposition. 1675-1682
Session 12B
- Sourav Chakraborty, David García-Soriano
Nearly Tight Bounds for Testing Function Isomorphism. 1683-1702 - Pavol Hell, Arash Rafiey:
The Dichotomy of List Homomorphisms for Digraphs. 1703-1713 - Jin-yi Cai, Pinyan Lu
Dichotomy for Holant* Problems of Boolean Domain. 1714-1728 - Kazuyuki Amano:
Bounding the Randomized Decision Tree Complexity of Read-Once Boolean Functions. 1729-1744
Session 12C
- Peyman Afshani, Norbert Zeh:
Improved Space Bounds for Cache-Oblivious Range Reporting. 1745-1758 - Maarten Löffler, Wolfgang Mulzer:
Triangulating the Square and Squaring the Triangle: Quadtrees and Delaunay Triangulations are Equivalent. 1759-1777 - Esther Ezra, Boris Aronov, Micha Sharir:
Improved Bound for the Union of Fat Triangles. 1778-1785
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-11-19 20:32 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: