23. SODA 2012:
Kyoto,
Japan
Yuval Rabani (Ed.):
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012.
SIAM 2012
- Martin Cadek, Marek Krcál, Jirí Matousek, Francis Sergeraert, Lukás Vokrínek, Uli Wagner:
Computing all maps into a sphere.
1-10
- Menelaos I. Karavelas, Eleni Tzanaki:
The maximum number of faces of the Minkowski sum of two convex polytopes.
11-28
- Sunil Arya, Guilherme Dias da Fonseca, David M. Mount:
Polytope approximation and the Mahler volume.
29-42
- James R. Lee, Arnaud de Mesmay, Mohammad Moharrami:
Dimension reduction for finite trees in l1.
43-50
- Ilan Newman, Yuri Rabinovich:
On multiplicative λ-approximations and some geometric applications.
51-67
- Holger Dell, Dániel Marx:
Kernelization of packing problems.
68-81
- Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos:
Linear kernels for (connected) dominating set on H-minor-free graphs.
82-93
- Stefan Kratsch, Magnus Wahlström:
Compression via matroids: a randomized polynomial kernel for odd cycle transversal.
94-103
- Danny Hermelin, Xi Wu:
Weak compositions and their applications to polynomial lower bounds for kernelization.
104-113
- Stefan Kratsch:
Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem.
114-122
- Telikepalli Kavitha:
Popularity vs maximum cardinality in the stable marriage setting.
123-134
- Tamás Fleiner, Naoyuki Kamiyama:
A matroid approach to stable matchings with lower quotas.
135-142
- Eyal Kushilevitz, Steve Lu, Rafail Ostrovsky:
On the (in)security of hash-based oblivious RAM and a new balancing scheme.
143-156
- Michael T. Goodrich, Michael Mitzenmacher, Olga Ohrimenko, Roberto Tamassia:
Privacy-preserving group data access via stateless oblivious RAM simulation.
157-167
- Moritz Hardt, Guy N. Rothblum, Rocco A. Servedio:
Private data release via learning thresholds.
168-187
- Martin Grohe:
Structural and logical approaches to the graph isomorphism problem.
188
- Aaron Bernstein:
Near linear time (1 + ε)-approximation for restricted shortest paths in undirected graphs.
189-201
- Christian Wulff-Nilsen:
Approximate distance oracles with improved preprocessing time.
202-208
- Shay Mozes, Christian Sommer:
Exact distance oracles for planar graphs.
209-222
- Surender Baswana, Utkarsh Lath, Anuradha S. Mehta:
Single source distance oracle for planar digraphs avoiding a failed node or link.
223-232
- Vincenzo Bonifaci, Kurt Mehlhorn, Girish Varma:
Physarum can compute shortest paths.
233-240
- Amin Coja-Oghlan, Lenka Zdeborová:
The condensation transition in random hypergraph 2-coloring.
241-250
- Marc Lelarge:
A new approach to the orientation of random hypergraphs.
251-264
- Hervé Daudé, Conrado Martínez, Vonjy Rasendrahasina, Vlady Ravelomanana:
The MAX-CUT of sparse random graphs.
265-271
- Charilaos Efthymiou:
A simple algorithm for random colouring G(n, d/n) using (2 + ε)d colours.
272-280
- Michael Drmota, Omer Giménez, Marc Noy, Konstantinos Panagiotou, Angelika Steger:
The maximum degree of random planar graphs.
281-287
- Guillaume Moroz, Boris Aronov:
Computing the distance between piecewise-linear bivariate functions.
288-293
- Adrian Dumitrescu, Csaba D. Tóth:
Packing anchored rectangles.
294-305
- R. Sharathkumar, Pankaj K. Agarwal:
Algorithms for the transportation problem in geometric settings.
306-317
- Anne Driemel, Sariel Har-Peled:
Jaywalking your dog: computing the Fréchet distance with shortcuts.
318-337
- Haim Kaplan, Shay Mozes, Yahav Nussbaum, Micha Sharir:
Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications.
338-355
- Thomas Rothvoß:
The entropy rounding method in approximation algorithms.
356-372
- Prasad Raghavendra, Ning Tan:
Approximating CSPs with global cardinality constraints using SDP hierarchies.
373-387
- Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan, Venkatesan Guruswami, Yuan Zhou:
Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph.
388-405
- Eden Chlamtac, Ishay Haviv:
Linear index coding via semidefinite programming.
406-419
- Konstantin Makarychev, Warren Schudy, Maxim Sviridenko:
Concentration inequalities for nonlinear matroid intersection.
420-436
- Warren Schudy, Maxim Sviridenko:
Concentration and moment inequalities for polynomials of independent random variables.
437-446
- Alexandr Andoni, Huy L. Nguyen:
Width of points in the streaming model.
447-452
- Andrew McGregor, Paul Valiant:
The shifting sands algorithm.
453-458
- Kook Jin Ahn, Sudipto Guha, Andrew McGregor:
Analyzing graph structure via linear measurements.
459-467
- Ashish Goel, Michael Kapralov, Sanjeev Khanna:
On the communication and streaming complexity of maximum bipartite matching.
468-485
- Jeff M. Phillips, Elad Verbin, Qin Zhang:
Lower bounds for number-in-hand multiparty communication complexity, made easy.
486-501
- Chen Avin, Asaf Cohen, Yoram Haddad, Erez Kantor, Zvi Lotker, Merav Parter, David Peleg:
SINR diagram with interference cancellation.
502-515
- Magnús M. Halldórsson, Pradipta Mitra:
Wireless connectivity and capacity.
516-526
- Yoann Dieudonné, Andrzej Pelc, David Peleg:
Gathering despite mischief.
527-540
- Po-Shen Loh, Eyal Lubetzky:
Stochastic coalescence in logarithmic time.
541-550
- John Augustine, Gopal Pandurangan, Peter Robinson, Eli Upfal:
Towards robust and efficient computation in dynamic peer-to-peer networks.
551-569
- John Iacono, Mihai Patrascu:
Using hashing to solve the dictionary problem.
570-582
- Kasper Green Larsen, Rasmus Pagh:
I/O-efficient data structures for colored range and prefix reporting.
583-592
- Sébastien Collette, John Iacono, Stefan Langerman:
Confluent persistence revisited.
593-601
- Gerth Stølting Brodal, Konstantinos Tsakalidis, Spyros Sioutas, Kostas Tsichlas:
Fully persistent B-trees.
602-614
- Arkadev Chattopadhyay, Jeff Edmonds, Faith Ellen, Toniann Pitassi:
A little advice can be very helpful.
615-625
- David Eisenstat, Philip N. Klein, Claire Mathieu:
An efficient polynomial-time approximation scheme for Steiner forest in planar graphs.
626-638
- MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Philip N. Klein, Claire Mathieu:
A polynomial-time approximation scheme for planar multiway cut.
639-655
- Marcin Kaminski, Naomi Nishimura:
Finding an induced path of given parity in planar graphs in polynomial time.
656-670
- Ken-ichi Kawarabayashi, Kenta Ozeki:
Spanning closed walks and TSP in 3-connected planar graphs.
671-682
- Frank Kammer, Torsten Tholey:
Approximate tree decompositions of planar graphs in linear time.
683-698
- Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu:
Bypassing UGC from some optimal geometric inapproximability results.
699-717
- Ravishankar Krishnaswamy, Maxim Sviridenko:
Inapproximability of the multi-level uncapacitated facility location problem.
718-734
- Preyas Popat, Yi Wu:
On the hardness of pricing loss-leaders.
735-749
- Vladimir Kolmogorov, Stanislav Zivny:
The complexity of conservative valued CSPs.
750-759
- Morteza Ibrahimi, Yashodhan Kanoria, Matt Kraning, Andrea Montanari:
The set of solutions of random XORSAT formulae.
760-779
- Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, Yuan Zhou:
Approximation algorithms and hardness of the k-route cut problem.
780-799
- Petr Kolman, Christian Scheideler:
Approximate duality of multicommodity multiroute flows and cuts: single source case.
800-810
- Arman Yousefi, Neal E. Young:
On a linear program for minimum-weight triangulation.
811-823
- Amit Kumar:
Constant factor approximation algorithm for the knapsack median problem.
824-832
- Liam Roditty, Virginia Vassilevska Williams:
Subquadratic time approximation algorithms for the girth.
833-845
- Berthold Vöcking:
A universally-truthful approximation scheme for multi-unit auctions.
846-855
- Shuchi Chawla, Jason D. Hartline, Balasubramanian Sivan:
Optimal crowdsourcing contests.
856-868
- Renato Paes Leme, Vasilis Syrgkanis, Éva Tardos:
Sequential auctions and externalities.
869-886
- Bach Q. Ha, Jason D. Hartline:
Mechanism design via consensus estimates, cross checking, and profit extraction.
887-895
- Konstantinos Georgiou, Chaitanya Swamy:
Black-box reductions for cost-sharing mechanism design.
896-913
- Andreas Björklund:
Counting perfect matchings as fast as Ryser.
914-921
- Liang Li, Pinyan Lu, Yitong Yin:
Approximate counting via correlation decay in spin systems.
922-940
- Alistair Sinclair, Piyush Srivastava, Marc Thurley:
Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs.
941-953
- Josep Díaz, Leslie Ann Goldberg, George B. Mertzios, David Richerby, Maria J. Serna, Paul G. Spirakis:
Approximating fixation probabilities in the generalized Moran process.
954-960
- Russell Impagliazzo, William Matthews, Ramamohan Paturi:
A satisfiability algorithm for AC0.
961-972
- Vijay V. Vazirani:
The notion of a rational convex program, and an algorithm for the Arrow-Debreu Nash bargaining game.
973-992
- Amos Fiat, Elias Koutsoupias, Katrina Ligett, Yishay Mansour, Svetlana Olonetsky:
Beyond myopic best response (in Cournot competition).
993-1005
- Vincenzo Auletta, Diodato Ferraioli, Francesco Pasquale, Giuseppe Persiano:
Metastability of logit dynamics for coordination games.
1006-1024
- Ashwinkumar Badanidiyuru, Shahar Dobzinski, Hu Fu, Robert Kleinberg, Noam Nisan, Tim Roughgarden:
Sketching valuation functions.
1025-1035
- Flavio Chierichetti, Jon M. Kleinberg:
Voting with limited information and many alternatives.
1036-1055
- Nicolas Broutin, Ralph Neininger, Henning Sulzbach:
Partial match queries in random quadtrees.
1056-1065
- Gonzalo Navarro, Yakov Nekrich:
Top-k document retrieval in optimal time and linear space.
1066-1077
- Flavio Chierichetti, Ravi Kumar:
LSH-preserving functions and their applications.
1078-1094
- Tomasz Kociumaka, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen:
A linear time algorithm for seeds computation.
1095-1112
- Josef Cibulka, Jan Kyncl:
Tight bounds on the maximum size of a set of permutations with bounded VC-dimension.
1113-1122
- Krzysztof Onak, Dana Ron, Michal Rosen, Ronitt Rubinfeld:
A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size.
1123-1131
- Noga Alon, Ronitt Rubinfeld, Shai Vardi, Ning Xie:
Space-efficient local computation algorithms.
1132-1139
- Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira:
Testing odd-cycle-freeness in Boolean functions.
1140-1149
- Silvio Frischknecht, Stephan Holzer, Roger Wattenhofer:
Networks cannot compute their diameter in sublinear time.
1150-1162
- Ho-Lin Chen, David Doty:
Parallelism and time in hierarchical self-assembly.
1163-1182
- Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price:
Simple and practical algorithm for sparse Fourier transform.
1183-1194
- Daniel M. Kane, Jelani Nelson:
Sparser Johnson-Lindenstrauss transforms.
1195-1206
- Venkatesan Guruswami, Ali Kemal Sinop:
Optimal column-based low-rank matrix reconstruction.
1207-1214
- Ely Porat, Martin J. Strauss:
Sublinear time, measurement-optimal, sparse recovery for all.
1215-1227
- S. Anand, Naveen Garg, Amit Kumar:
Resource augmentation for weighted flow-time explained by dual fitting.
1228-1241
- Anupam Gupta, Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, Kirk Pruhs:
Scheduling heterogeneous processors isn't as easy as you think.
1242-1253
- Sungjin Im, Benjamin Moseley, Kirk Pruhs:
Online scheduling with general cost functions.
1254-1265
- Susanne Albers, Antonios Antoniadis:
Race to idle: new algorithms for speed scaling with a sleep state.
1266-1285
- Hsien-Chih Chang, Hsueh-I Lu:
A faster algorithm to recognize even-hole-free graphs.
1286-1297
- Yuri Faenza, Gianpaolo Oriolo, Gautier Stauffer:
Separating stable sets in claw-free graphs via Padberg-Rao and compact linear programs.
1298-1308
- Jeff Erickson, Kyle Fox, Amir Nayyeri:
Global minimum cuts in surface embedded graphs.
1309-1318
- Prosenjit Bose, Rolf Fagerberg, André van Renssen, Sander Verdonschot:
Competitive routing in the half-θ6-graph.
1319-1328
- Kasturi Varadarajan, Xin Xiao:
A near-linear algorithm for projective clustering integer points.
1329-1342
- Dan Feldman, Leonard J. Schulman:
Data reduction for weighted and outlier-resistant clustering.
1343-1354
- Paul Bendich, Bei Wang, Sayan Mukherjee:
Local homology transfer and stratification learning.
1355-1370
- Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio:
Learning k-modal distributions via testing.
1371-1385
- Krishnendu Chatterjee, Monika Henzinger:
An O(n2) time algorithm for alternating Büchi games.
1386-1399
- Chien-Chung Huang, Telikepalli Kavitha:
Efficient algorithms for maximum weight matchings in general graphs with small edge weights.
1400-1412
- Ran Duan, Hsin-Hao Su:
A scaling algorithm for maximum weight matching in bipartite graphs.
1413-1424
- Ken-ichi Kawarabayashi, Yusuke Kobayashi:
List-coloring graphs without subdivisions and without immersions.
1425-1435
- Andreas Björklund, Mikko Koivisto, Thore Husfeldt, Jesper Nederlof, Petteri Kaski, Pekka Parviainen:
Fast zeta transforms for lattices with few irreducibles.
1436-1444
- Daniel Dadush, Santosh Vempala:
Deterministic construction of an approximate M-ellipsoid and its applications to derandomizing lattice algorithms.
1445-1456
- Qi Cheng, Shuhong Gao, Daqing Wan:
Constructing high order elements through subspace polynomials.
1457-1463
- François Le Gall:
Improved output-sensitive quantum algorithms for Boolean matrix multiplication.
1464-1476
- Frans Schalekamp, David P. Williamson, Anke van Zuylen:
A proof of the Boyd-Carr conjecture.
1477-1486
- Siddharth Barman, Shuchi Chawla:
Traffic-redundancy aware network design.
1487-1498
- Joseph Cheriyan, Bundit Laekhanukit, Guyslain Naves, Adrian Vetta:
Approximating rooted Steiner networks.
1499-1511
- Rico Zenklusen:
Matroidal degree-bounded minimum spanning trees.
1512-1521
- Anupam Gupta, Ravishankar Krishnaswamy, Viswanath Nagarajan, R. Ravi:
Approximation algorithms for stochastic orienteering.
1522-1538
- Daniel Johannsen, Michael Krivelevich, Wojciech Samotij:
Expanders are universal for the class of all spanning trees.
1539-1551
- Stephan Kreutzer, Siamak Tazari:
Directed nowhere dense classes of graphs.
1552-1562
- Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh:
Bidimensionality and geometric graphs.
1563-1575
- Timothy M. Chan, Elyot Grant, Jochen Könemann, Malcolm Sharpe:
Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling.
1576-1585
- Mahdi Cheraghchi, Adam Klivans, Pravesh Kothari, Homin K. Lee:
Submodular functions are noise stable.
1586-1592
- Ayush Choure, Sundar Vishwanathan:
Random walks, electric networks and the transience class problem of sandpiles.
1593-1611
- Henry Lam, Zhenming Liu, Michael Mitzenmacher, Xiaorui Sun, Yajun Wang:
Information dissemination via random walks in d-dimensional space.
1612-1622
- George Giakkoupis, Thomas Sauerwald:
Rumor spreading and vertex expansion.
1623-1641
- Nikolaos Fountoulakis, Konstantinos Panagiotou, Thomas Sauerwald:
Ultra-fast rumor spreading in social networks.
1642-1660
- Louigi Addario-Berry, Tao Lei:
The mixing time of the Newman: Watts small world.
1661-1668
- Gabriel Moruz, Andrei Negoescu:
Outperforming LRU via competitive analysis on parametrized inputs for paging.
1669-1680
- Anna Adamaszek, Artur Czumaj, Matthias Englert, Harald Räcke:
An O(log k)-competitive algorithm for generalized caching.
1681-1689
- Vahab S. Mirrokni, Shayan Oveis Gharan, Morteza Zadimoghaddam:
Simultaneous approximations for adversarial and stochastic online budgeted allocation.
1690-1701
- Sourav Chakraborty, Oded Lachish:
Improved competitive ratio for the matroid secretary problem.
1702-1712
- Rajesh Hemant Chitnis, MohammadTaghi Hajiaghayi, Dániel Marx:
Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset.
1713-1725
- Naonori Kakimura, Ken-ichi Kawarabayashi, Yusuke Kobayashi:
Erdös-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing.
1726-1736
- Fedor V. Fomin, Yngve Villanger:
Subexponential parameterized algorithm for minimum fill-in.
1737-1746
- Andreas Björklund, Thore Husfeldt, Nina Taslaman:
Shortest cycle through specified elements.
1747-1753
Last update Fri May 25 08:40:52 2012
CET by the DBLP Team —
Data released under the ODC-BY 1.0 license — See also our legal information page