default search action
23rd SODA 2012: Kyoto, Japan
- Yuval Rabani:
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012. SIAM 2012, ISBN 978-1-61197-210-8 - 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
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
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
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
Jaywalking your dog: computing the Fréchet distance with shortcuts. 318-337 - Haim Kaplan, Shay Mozes
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
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
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 Zivný:
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
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
Approximating fixation probabilities in the generalized Moran process. 954-960 - Russell Impagliazzo
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
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
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
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
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 R. 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
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
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
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
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
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-22 19:30 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: