21. SODA 2010: Austin, Texas, USA

Session 1A

• Elmar Langetepe:
  On the Optimality of Spiral Search. 1-12
  
• Noa Avigdor-Elgrabli, Yuval Rabani:
  An Improved Competitive Algorithm for Reordering Buffer Management. 13-21
  
• Jurek Czyzowicz, Arnaud Labourel, Andrzej Pelc:
  How to Meet Asynchronously (Almost) Everywhere. 22-30
  
• Bahman Bahmani, Aranyak Mehta, Rajeev Motwani:
  A 1.43-Competitive Online Graph Edge Coloring Algorithm in the Random Order Arrival Model. 31-39
  
• Nikhil Bansal, Niv Buchbinder, Joseph Naor:
  Towards the Randomized k-Server Conjecture: A Primal-Dual Approach. 40-55
  

Session 1B

• Michal Adamaszek, Artur Czumaj, Christian Sohler:
  Testing Monotone Continuous Distributions on High-dimensional Real Cubes. 56-65
  
• Carlos Hoppen, Yoshiharu Kohayakawa, Carlos Gustavo T. de A. Moreira, Rudini Menezes Sampaio:
  Property Testing and Parameter Testing for Permutations. 66-75
  
• Alexandr Andoni, Huy L. Nguyen:
  Near-Optimal Sublinear Time Algorithms for Ulam Distance. 76-86
  
• Arnab Bhattacharyya, Ning Xie:
  Lower Bounds for Testing Triangle-freeness in Boolean Functions. 87-98
  
• Mira Gonen, Dana Ron, Yuval Shavitt:
  Counting Stars and Other Small Subgraphs in Sublinear Time. 99-116
  

Session 1C

• Mihai Patrascu, Emanuele Viola:
  Cell-Probe Lower Bounds for Succinct Partial Sums. 117-122
  
• Ke Yi, Qin Zhang:
  On the Cell Probe Complexity of Dynamic Membership. 123-133
  
• Kunihiko Sadakane, Gonzalo Navarro:
  Fully-Functional Succinct Trees. 134-149
  
• Hao Yuan, Mikhail J. Atallah:
  Data Structures for Range Minimum Queries in Multidimensional Arrays. 150-160
  
• Timothy M. Chan, Mihai Patrascu:
  Counting Inversions, Offline Orthogonal Range Counting, and Related Problems. 161-173
  

Session 2

• Cynthia Dwork:
  Differential Privacy in New Settings. 174-183
  

Session 3A

• Alexandr Andoni, T. S. Jayram, Mihai Patrascu:
  Lower Bounds for Edit Distance and Product Metrics via Poincaré-Type Inequalities. 184-192
  
• James R. Lee, Anastasios Sidiropoulos:
  Genus and the Geometry of the Cut Graph. 193-201
  
• Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati, Vít Jelínek, Jan Kratochvíl, Maurizio Patrignani, Ignaz Rutter:
  Testing Planarity of Partially Embedded Graphs. 202-221
  
• Jeff Edmonds, Anastasios Sidiropoulos, Anastasios Zouzias:
  Inapproximability for Planar Embedding Problems. 222-235
  
• Manor Mendel, Assaf Naor:
  Towards a Calculus for Non-Linear Spectral Gaps. 236-255
  

Session 3B

• T.-H. Hubert Chan, Khaled M. Elbassioni:
  A QPTAS for TSP with Fat Weakly Disjoint Neighborhoods in Doubling Metrics. 256-267
  
• David Gamarnik, David Goldberg, Theophane Weber:
  PTAS for Maximum Weight Independent Set Problem with Random Weights in Bounded Degree Graphs. 268-278
  
• David Gamarnik, Devavrat Shah, Yehua Wei:
  Belief Propagation for Min-cost Network Flow: Convergence & Correctness. 279-292
  
• Flavio Chierichetti, Ravi Kumar, Sandeep Pandey, Sergei Vassilvitskii:
  Finding the Jaccard Median. 293-311
  
• Dries R. Goossens, Sergey Polyakovskiy, Frits C. R. Spieksma, Gerhard J. Woeginger:
  The Focus of Attention Problem. 312-317
  

Session 3C

• Ken-ichi Kawarabayashi, Zhentao Li, Bruce A. Reed:
  Recognizing a Totally Odd K₄-subdivision, Parity 2-disjoint Rooted Paths and a Parity Cycle Through Specified Elements. 318-328
  
• Erik D. Demaine, MohammadTaghi Hajiaghayi, Ken-ichi Kawarabayashi:
  Decomposition, Approximation, and Coloring of Odd-Minor-Free Graphs. 329-344
  
• Ken-ichi Kawarabayashi, Yusuke Kobayashi:
  The Edge Disjoint Paths Problem in Eulerian Graphs and 4-edge-connected Graphs. 345-353
  
• Stephan Kreutzer, Siamak Tazari:
  On Brambles, Grid-Like Minors, and Parameterized Intractability of Monadic Second-Order Logic. 354-364
  
• Ken-ichi Kawarabayashi, Bruce A. Reed:
  An (almost) Linear Time Algorithm for Odd Cyles Transversal. 365-378
  

Best Paper Presentation

• Arash Asadpour, Michel X. Goemans, Aleksander Madry, Shayan Oveis Gharan, Amin Saberi:
  An O(log n/ log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem. 379-389
  

Session 4A

• Aparna Das, Claire Mathieu:
  A Quasi-polynomial Time Approximation Scheme for Euclidean Capacitated Vehicle Routing. 390-403
  
• Siddharth Barman, Shuchi Chawla:
  Region Growing for Multi-Route Cuts. 404-418
  
• Zachary Friggstad, Mohammad R. Salavatipour, Zoya Svitkina:
  Asymmetric Traveling Salesman Path and Directed Latency Problems. 419-428
  
• Aaron Archer, Anna Blasiak:
  Improved Approximation Algorithms for the Minimum Latency Problem via Prize-Collecting Strolls. 429-447
  

Session 4B

• Martin Rötteler:
  Quantum Algorithms for Highly Non-Linear Boolean Functions. 448-457
  
• Pierre Fraigniaud, Amos Korman:
  Compact Ancestry Labeling Schemes for XML Trees. 458-466
  
• Raphael Yuster:
  Generating a d-dimensional Linear Subspace Efficiently. 467-470
  
• Kirsten Eisenträger, Sean Hallgren:
  Algorithms for Ray Class Groups and Hilbert Class Fields. 471-483
  

Session 4C

• Mikko Koivisto, Pekka Parviainen:
  A Space-Time Tradeoff for Permutation Problems. 484-492
  
• Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh:
  Algorithmic Lower Bounds for Problems Parameterized with Clique-Width. 493-502
  
• Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos:
  Bidimensionality and Kernels. 503-510
  
• Noga Alon, Gregory Gutin, Eun Jung Kim, Stefan Szeider, Anders Yeo:
  Solving MAX-r-SAT Above a Tight Lower Bound. 511-517
  

Session 5A

• David Buchfuhrer, Shaddin Dughmi, Hu Fu, Robert Kleinberg, Elchanan Mossel, Christos H. Papadimitriou, Michael Schapira, Yaron Singer, Christopher Umans:
  Inapproximability for VCG-Based Combinatorial Auctions. 518-536
  
• Brendan Lucier, Allan Borodin:
  Price of Anarchy for Greedy Auctions. 537-553
  
• Sayan Bhattacharya, Vincent Conitzer, Kamesh Munagala, Lirong Xia:
  Incentive Compatible Budget Elicitation in Multi-unit Auctions. 554-572
  
• Fabrizio Grandoni, Piotr Krysta, Stefano Leonardi, Carmine Ventre:
  Utilitarian Mechanism Design for Multi-Objective Optimization. 573-584
  
• Patrick Briest, Shuchi Chawla, Robert Kleinberg, S. Matthew Weinberg:
  Pricing Randomized Allocations. 585-597
  

Session 5B

• Michael Langberg, Leonard J. Schulman:
  Universal epsilon-approximators for Integrals. 598-607
  
• Hanna Mazzawi:
  Optimally Reconstructing Weighted Graphs Using Queries. 608-615
  
• Chao-Kai Chiang, Chi-Jen Lu:
  Online Learning with Queries. 616-629
  
• Dan Feldman, Morteza Monemizadeh, Christian Sohler, David P. Woodruff:
  Coresets and Sketches for High Dimensional Subspace Approximation Problems. 630-649
  
• Tamal K. Dey, Pawas Ranjan, Yusu Wang:
  Convergence, Stability, and Discrete Approximation of Laplace Spectra. 650-663
  

Session 5C

• Subhash Khot, Assaf Naor:
  Sharp Kernel Clustering Algorithms and Their Associated Grothendieck Inequalities. 664-683
  
• David Steurer:
  Fast SDP Algorithms for Constraint Satisfaction Problems. 684-697
  
• Anthony Man-Cho So:
  Probabilistic Analysis of the Semidefinite Relaxation Detector in Digital Communications. 698-711
  
• Claire Mathieu, Warren Schudy:
  Correlation Clustering with Noisy Input. 712-728
  
• Tom Coleman, Anthony Wirth:
  A Polynomial Time Approximation Scheme for k-Consensus Clustering. 729-740
  

Session 6

• Noam Nisan:
  Google's Auction for TV Ads. 741
  

Session 7A

• Aaron Bernstein:
  A Nearly Optimal Algorithm for Approximating Replacement Paths and k Shortest Simple Paths in General Graphs. 742-755
  
• Christian Wulff-Nilsen:
  Solving the Replacement Paths Problem for Planar Directed Graphs in O(n log n) Time. 756-765
  
• Jeff Edmonds, Supratik Chakraborty:
  Bounding Variance and Expectation of Longest Path Lengths in DAGs. 766-781
  
• Ittai Abraham, Amos Fiat, Andrew V. Goldberg, Renato Fonseca F. Werneck:
  Highway Dimension, Shortest Paths, and Provably Efficient Algorithms. 782-793
  
• Jeff Erickson:
  Maximum Flows and Parametric Shortest Paths in Planar Graphs. 794-804
  

Session 7B

• Aaron Roth, Maria-Florina Balcan, Adam Kalai, Yishay Mansour:
  On the Equilibria of Alternating Move Games. 805-816
  
• Yossi Azar, Nikhil R. Devanur, Kamal Jain, Yuval Rabani:
  Monotonicity in Bargaining Networks. 817-826
  
• Robert Kleinberg, Aleksandrs Slivkins:
  Sharp Dichotomies for Regret Minimization in Metric Spaces. 827-846
  
• Hugo Gimbert, Florian Horn:
  Solving Simple Stochastic Tail Games. 847-862
  
• Tomás Brázdil, Václav Brozek, Kousha Etessami, Antonín Kucera, Dominik Wojtczak:
  One-Counter Markov Decision Processes. 863-874
  

Session 7C

• Seth Pettie:
  On Nonlinear Forbidden 0-1 Matrices: A Refutation of a Füredi-Hajnal Conjecture. 875-885
  
• Michael Elkin:
  An Improved Construction of Progression-Free Sets. 886-905
  
• Antoine Vigneron:
  Geometric Optimization and Sums of Algebraic Functions. 906-917
  
• Petr Hlinený, Markus Chimani:
  Approximating the Crossing Number of Graphs Embeddable in Any Orientable Surface. 918-927
  
• Ciprian Borcea, Ileana Streinu:
  How Far Can You Reach? 928-937
  

Session 8A

• Howard J. Karloff, Siddharth Suri, Sergei Vassilvitskii:
  A Model of Computation for MapReduce. 938-948
  
• Fabian Kuhn, Konstantinos Panagiotou, Joel Spencer, Angelika Steger:
  Synchrony and Asynchrony in Neural Networks. 949-964
  
• Seth Gilbert, Dariusz R. Kowalski:
  Distributed Agreement with Optimal Communication Complexity. 965-977
  
• Constantinos Daskalakis, Ilias Diakonikolas, Mihalis Yannakakis:
  How Good is the Chord Algorithm?. 978-991
  
• Karthekeyan Chandrasekaran, Navin Goyal, Bernhard Haeupler:
  Deterministic Algorithms for the Lovász Local Lemma. 992-1004
  

Session 8B

• George Christodoulou, Annamária Kovács:
  A Deterministic Truthful PTAS for Scheduling Related Machines. 1005-1016
  
• Risi Kondor:
  A Fourier Space Algorithm for Solving Quadratic Assignment Problems. 1017-1028
  
• Friedrich Eisenbrand, Thomas Rothvoß:
  EDF-schedulability of Synchronous Periodic Task Systems is coNP-hard. 1029-1034
  
• Sagi Snir, Raphael Yuster:
  Reconstructing Approximate Phylogenetic Trees from Quartet Samples. 1035-1044
  
• Zachary Abel, Nadia Benbernou, Mirela Damian, Erik D. Demaine, Martin L. Demaine, Robin Y. Flatland, Scott D. Kominers, Robert T. Schweller:
  Shape Replication through Self-Assembly and RNase Enzymes. 1045-1064
  

Session 8C

• Mihai Patrascu, Ryan Williams:
  On the Possibility of Faster SAT Algorithms. 1065-1075
  
• David Eppstein:
  Paired Approximation Problems and Incompatible Inapproximabilities. 1076-1086
  
• Shipra Agrawal, Yichuan Ding, Amin Saberi, Yinyu Ye:
  Correlation Robust Stochastic Optimization. 1087-1096
  
• Neil Olver, F. Bruce Shepherd:
  Approximability of Robust Network Design. 1097-1105
  
• Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, Kunal Talwar:
  Differentially Private Combinatorial Optimization. 1106-1125
  

Session 9A

• Piotr Indyk, Hung Q. Ngo, Atri Rudra:
  Efficiently Decodable Non-adaptive Group Testing. 1126-1142
  
• Morteza Monemizadeh, David P. Woodruff:
  1-Pass Relative-Error L_p-Sampling with Applications. 1143-1160
  
• Daniel M. Kane, Jelani Nelson, David P. Woodruff:
  On the Exact Space Complexity of Sketching and Streaming Small Norms. 1161-1178
  
• Tyler Neylon:
  A Locality-Sensitive Hash for Real Vectors. 1179-1189
  
• Khanh Do Ba, Piotr Indyk, Eric Price, David P. Woodruff:
  Lower Bounds for Sparse Recovery. 1190-1197
  

Session 9B

• Chandra Chekuri, F. Bruce Shepherd, Christophe Weibel:
  Flow-Cut Gaps for Integer and Fractional Multiflows. 1198-1208
  
• S. M. Sadegh Tabatabaei Yazdi, Serap A. Savari:
  A Max-Flow/Min-Cut Algorithm for a Class of Wireless Networks. 1209-1226
  
• Friedrich Eisenbrand, Nicolai Hähnle, Dömötör Pálvölgyi, Gennady Shmonin:
  Testing Additive Integrality Gaps. 1227-1234
  
• Chien-Chung Huang:
  Classified Stable Matching. 1235-1253
  
• Gábor Pataki, Mustafa Tural, Erick B. Wong:
  Basis Reduction and the Complexity of Brand-and-Bound. 1254-1261
  

Session 9C

• Michael T. Goodrich:
  Randomized Shellsort: A Simple Oblivious Sorting Algorithm. 1262-1277
  
• Raimund Seidel:
  Data-Specific Analysis of String Sorting. 1278-1286
  
• Alexander Tiskin:
  Fast Distance Multiplication of Unit-Monge Matrices. 1287-1296
  
• Philip Bille, Mikkel Thorup:
  Regular Expression Matching with Multi-Strings and Intervals. 1297-1308
  
• Daniel Chen, Leonidas J. Guibas, John Hershberger, Jian Sun:
  Road Network Reconstruction for Organizing Paths. 1309-1320
  

Session 10

• Emmanuel J. Candès:
  The Power of Convex Relaxation: The Surprising Stories of Matrix Completion and Compressed Sensing. 1321
  

Session 11A

• Sungjin Im, Benjamin Moseley:
  An Online Scalable Algorithm for Average Flow Time in Broadcast Scheduling. 1322-1333
  
• Parinya Chalermsook, Julia Chuzhoy:
  Resource Minimization for Fire Containment. 1334-1349
  
• Vincenzo Bonifaci, Ho-Leung Chan, Alberto Marchetti-Spaccamela, Nicole Megow:
  Algorithms and Complexity for Periodic Real-Time Scheduling. 1350-1359
  
• Samir Khuller, Jian Li, Barna Saha:
  Energy Efficient Scheduling via Partial Shutdown. 1360-1372
  
• Christine Chung, Tim Nonner, Alexander Souza:
  SRPT is 1.86-Competitive for Completion Time Scheduling. 1373-1388
  

Session 11B

• Charles Bordenave, Marc Lelarge:
  The Rank of Diluted Random Graphs. 1389-1402
  
• Hamed Hatami, Michael Molloy:
  The Scaling Window for a Random Graph with a Given Degree Sequence. 1403-1411
  
• Milan Bradonjic, Robert Elsässer, Tobias Friedrich, Thomas Sauerwald, Alexandre Stauffer:
  Efficient Broadcast on Random Geometric Graphs. 1412-1421
  
• Petra Berenbrink, Colin Cooper, Robert Elsässer, Tomasz Radzik, Thomas Sauerwald:
  Speeding Up Random Walks with Neighborhood Exploration. 1422-1435
  
• Daniel Johannsen, Konstantinos Panagiotou:
  Vertices of Degree k in Random Maps. 1436-1447
  

Session 11C

• Gerth Stølting Brodal, Erik D. Demaine, Jeremy T. Fineman, John Iacono, Stefan Langerman, J. Ian Munro:
  Cache-Oblivious Dynamic Dictionaries with Update/Query Tradeoffs. 1448-1456
  
• Seth Pettie:
  Applications of Forbidden 0-1 Matrices to Search Tree and Path Compression-Based Data Structures. 1457-1457
  
• Daniele Micciancio, Panagiotis Voulgaris:
  Faster Exponential Time Algorithms for the Shortest Vector Problem. 1468-1480
  
• Pankaj K. Agarwal, R. Sharathkumar:
  Streaming Algorithms for Extent Problems in High Dimensions. 1481-1489
  
• Siddhartha Sen, Robert Endre Tarjan:
  Deletion Without Rebalancing in Balanced Binary Trees. 1490-1499
  

Session 12A

• Yuk Hei Chan, Lap Chi Lau:
  On Linear and Semidefinite Programming Relaxations for Hypergraph Matching. 1500-1511
  
• Attila Bernáth, Roland Grappe, Zoltán Szigeti:
  Partition Constrained Covering of a Symmetric Crossing Supermodular Function by a Graph. 1512-1520
  
• Anupam Gupta, Ravishankar Krishnaswamy, R. Ravi:
  Tree Embeddings for Two-Edge-Connected Network Design. 1521-1538
  
• Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy:
  A Constant Factor Approximation Algorithm for Generalized Min-Sum Set Cover. 1539-1545
  

Session 12B

• Kenneth L. Clarkson, Wolfgang Mulzer, C. Seshadhri:
  Self-improving Algorithms for Convex Hulls. 1546-1565
  
• Adrian Dumitrescu, Minghui Jiang:
  The Forest Hiding Problem. 1566-1579
  
• James King, Erik Krohn:
  Terrain Guarding is NP-Hard. 1580-1593
  
• Chao Chen, Daniel Freedman:
  Hardness Results for Homology Localization. 1594-1604
  
• Sergey Bereg:
  Orthogonal Ham-Sandwich Theorem in R³. 1605-1612
  

Session 12C

• Yuval Peres, Kunal Talwar, Udi Wieder:
  The (1 + beta)-Choice Process and Weighted Balls-into-Bins. 1613-1619
  
• Tobias Friedrich, Martin Gairing, Thomas Sauerwald:
  Quasirandom Load Balancing. 1620-1629
  
• Karthekeyan Chandrasekaran, Daniel Dadush, Santosh Vempala:
  Thin Partitions: Isoperimetric Inequalities and a Sampling Algorithm for Star Shaped Bodies. 1630-1645
  
• Prasad Tetali, Juan Carlos Vera, Eric Vigoda, Linji Yang:
  Phase Transition for the Mixing Time of the Glauber Dynamics for Coloring Regular Trees. 1646-1656
  
• Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi:
  Rumour Spreading and Graph Conductance. 1657-1663
  

Last update Fri May 24 19:50:55 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page