23. SODA 2012: Kyoto, Japan

• 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 l₁. 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 AC⁰. 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-θ₆-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(n²) 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 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