Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID21st SODA 2010: Austin, Texas, USA
- Moses Charikar:
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010. SIAM 2010, ISBN 978-0-89871-701-3
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 A. 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 K4-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 Z. 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 M. Benbernou, Mirela Damian, Erik D. Demaine, Martin L. Demaine, Robin Y. Flatland, Scott Duke 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 Lp-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 Kemal 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-1467 - 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