default search action
26th SODA 2015: San Diego, CA, USA
- Piotr Indyk:
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015. SIAM 2015, ISBN 978-1-61197-374-7 - Front Matter.
- Nikhil Bansal:
Approximating independent sets in sparse graphs. 1-8 - Takuro Fukunaga:
Spider covers for prize-collecting network activation problem. 9-24 - Parinya Chalermsook, Fabrizio Grandoni
, Bundit Laekhanukit
On Survivable Set Connectivity. 25-36 - Martin Skutella:
A note on the ring loading problem. 37-46 - Jatin Batra, Naveen Garg
New Approximation Schemes for Unsplittable Flow on a Path. 47-58 - Zhiyi Huang
Welfare Maximization with Production Costs: A Primal Dual Approach. 59-72 - Ilan Reuven Cohen, Alon Eden, Amos Fiat, Lukasz Jez:
Pricing Online Decisions: Beyond Auctions. 73-91 - Andrew Chi-Chih Yao:
An n-to-1 Bidder Reduction for Multi-item Auctions and its Applications. 92-109 - Shahar Dobzinski, Hu Fu, Robert D. Kleinberg:
On the Complexity of Computing an Equilibrium in Combinatorial Auctions. 110-122 - Michal Feldman, Nick Gravin, Brendan Lucier:
Combinatorial Auctions via Posted Prices. 123-135 - Brad Ballinger, Mirela Damian, David Eppstein, Robin Y. Flatland, Jessica Ginepro, Thomas C. Hull:
Minimum Forcing Sets for Miura Folding Patterns. 136-147 - Sándor P. Fekete, Jacob Hendricks, Matthew J. Patitz
Universal Computation with Arbitrary Polyomino Tiles in Non-Cooperative Self-Assembly. 148-167 - Mickaël Buchet, Frédéric Chazal, Steve Y. Oudot, Donald R. Sheehy
Efficient and Robust Persistent Homology for Measures. 168-180 - Clément Maria, Steve Y. Oudot:
Zigzag Persistence via Reflections and Transpositions. 181-199 - Saladi Rahul:
Improved Bounds for Orthogonal Point Enclosure Query and Point Location in Orthogonal Subdivisions in ℝ3. 200-211 - Timothy M. Chan:
Speeding up the Four Russians Algorithm by About One More Logarithmic Factor. 212-217 - Amir Abboud, Richard Ryan Williams
More Applications of the Polynomial Method to Algorithm Design. 218-230 - Rahul Santhanam, Richard Ryan Williams
Beating Exhaustive Search for Quantified Boolean Formulas and Connections to Circuit Complexity. 231-241 - Chandra Chekuri, Julia Chuzhoy:
Degree-3 Treewidth Sparsifiers. 242-255 - Julia Chuzhoy:
Improved Bounds for the Flat Wall Theorem. 256-275 - Daniele Micciancio
Fast Lattice Point Enumeration with Minimal Overhead. 276-294 - Daniel Dadush
Short Paths on the Voronoi Graph and Closest Vector Problem with Preprocessing. 295-314 - Marco Di Summa, Friedrich Eisenbrand, Yuri Faenza, Carsten Moldenhauer:
On largest volume simplices and sub-determinants. 315-323 - Aleksandar Nikolov, Kunal Talwar:
Approximating Hereditary Discrepancy via Small Width Ellipsoids. 324-336 - Sepideh Mahabadi:
Approximate Nearest Line Search in High Dimensions. 337-354 - Michael Elkin, Seth Pettie, Hsin-Hao Su:
(2Δ - l)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting. 355-370 - Luca Becchetti
Plurality Consensus in the Gossip Model. 371-390 - Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan
Distributed Computation of Large-scale Graph Problems. 391-410 - Zeyu Guo
Gossip vs. Markov Chains, and Randomness-Efficient Rumor Spreading. 411-430 - Julian Shun, Yan Gu
Sequential Random Permutation, List Contraction and Tree Contraction are Highly Parallel. 431-448 - Yishay Mansour, Aviad Rubinstein, Moshe Tennenholtz:
Robust Probabilistic Inference. 449-460 - Amos Beimel, Kobbi Nissim
Learning Privately with Labeled and Unlabeled Examples. 461-477 - Anindya De, Ilias Diakonikolas, Rocco A. Servedio
Learning from satisfying assignments. 478-497 - Dana Dachman-Soled, Vitaly Feldman, Li-Yang Tan, Andrew Wan, Karl Wimmer:
Approximate resilience, monotonicity, and the complexity of agnostic learning. 498-511 - Ian Post, Chaitanya Swamy:
Linear Programming-based Approximation Algorithms for Multi-Vehicle Minimum Latency Problems (Extended Abstract). 512-531 - Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen
Internal Pattern Matching Queries in a Text and Applications. 532-551 - Raphaël Clifford, Markus Jalsenius, Benjamin Sach:
Cell-probe bounds for online edit distance and other pattern matching problems. 552-561 - Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda
A new characterization of maximal repetitions by Lyndon trees. 562-571 - Maxim A. Babenko, Pawel Gawrychowski, Tomasz Kociumaka, Tatiana Starikovskaya:
Wavelet Trees Meet Suffix Trees. 572-591 - Seth Pettie:
Sharp Bounds on Formation-free Sequences. 592-604 - Bingkai Lin:
The Parameterized Complexity of k-Biclique. 605-615 - Bart M. P. Jansen, Dániel Marx:
Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels. 616-629 - Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, M. S. Ramanujan, Saket Saurabh:
Solving d-SAT via Backdoors to Small Treewidth. 630-641 - Dániel Marx, Paul Wollan:
An exact characterization of tractable demand patterns for maximum disjoint path problems. 642-661 - Arkadiusz Socala:
Tight lower bound for the channel assignment problem. 662-675 - Guru Guruganesh, Laura Sanità, Chaitanya Swamy:
Improved Region-Growing and Combinatorial Algorithms for k-Route Cut Problems (Extended Abstract). 676-695 - Shi Li:
On Uniform Capacitated k-Median Beyond the Natural LP Relaxation. 696-707 - Hyung-Chan An, Ashkan Norouzi-Fard, Ola Svensson:
Dynamic Facility Location via Exponential Clocks. 708-721 - Jaroslaw Byrka, Krzysztof Fleszar, Bartosz Rybicki, Joachim Spoerhase:
Bi-Factor Approximation Algorithms for Hard Capacitated k-Median Problems. 722-736 - Jaroslaw Byrka, Thomas W. Pensyl, Bartosz Rybicki, Aravind Srinivasan, Khoa Trinh:
An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization. 737-756 - Haim Kaplan, Or Zamir, Uri Zwick:
The amortized cost of finding the minimum. 757-768 - Mayank Goswami, Allan Grønlund Jørgensen, Kasper Green Larsen, Rasmus Pagh
Approximate Range Emptiness in Constant Time and Optimal Space. 769-775 - Mohit Garg, Jaikumar Radhakrishnan:
Set membership with a few bit probes. 776-784 - Sayan Bhattacharya, Monika Henzinger, Giuseppe F. Italiano:
Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching. 785-804 - Michael Elkin, Seth Pettie:
A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs. 805-821 - Venkatesan Guruswami, Euiwoong Lee
Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs. 822-836 - Gábor Braun, Sebastian Pokutta:
The matching polytope does not admit fully-polynomial size relaxation schemes. 837-846 - Víctor Dalmau, Andrei A. Krokhin, Rajsekar Manokaran:
Towards a Characterization of Constant-Factor Approximable Min CSPs. 847-857 - Yann Disser, Martin Skutella:
The Simplex Algorithm is NP-mighty. 858-872 - Maryam Mirzakhani
Sperner's Colorings, Hypergraph Labeling Problems and Fair Division. 873-886 - Christos Boutsidis, Dan Garber, Zohar Shay Karnin, Edo Liberty:
Online Principal Components Analysis. 887-901 - Srinadh Bhojanapalli
Tighter Low-rank Approximation via Sampling the Leveraged Element. 902-920 - Kenneth L. Clarkson, David P. Woodruff:
Sketching for M-Estimators: A Unified Approach to Robust Regression. 921-939 - Ventsislav Chonev, Joël Ouaknine, James Worrell:
The Polyhedron-Hitting Problem. 940-956 - Joël Ouaknine, João Sousa Pinto
On Termination of Integer Linear Loops. 957-969 - Mark Braverman, Young Kun-Ko, Omri Weinstein:
Approximating the best Nash Equilibrium in no(log n)-time breaks the Exponential Time Hypothesis. 970-982 - Nikhil R. Devanur, Yuval Peres, Balasubramanian Sivan:
Perfect Bayesian Equilibria in Repeated Sales. 983-1002 - Yannai A. Gonczarowski, Noam Nisan, Rafail Ostrovsky, Will Rosenbaum
A Stable Marriage Requires Communication. 1003-1017 - Krishnendu Chatterjee, Rasmus Ibsen-Jensen
The Value 1 Problem Under Finite-memory Strategies for Concurrent Mean-payoff Games. 1018-1029 - Janardhan Kulkarni, Vahab S. Mirrokni:
Robust Price of Anarchy Bounds via LP and Fenchel Duality. 1030-1049 - Sungjin Im, Maxim Sviridenko:
New Approximations for Broadcast Scheduling via Variants of α-point Rounding. 1050-1069 - Sungjin Im, Shi Li, Benjamin Moseley, Eric Torng:
A Dynamic Programming Framework for Non-Preemptive Scheduling Problems on Multiple Machines [Extended Abstract]. 1070-1086 - Deeparnab Chakrabarty, Sanjeev Khanna, Shi Li:
On (1, ∊)-Restricted Assignment Makespan Minimization. 1087-1101 - Antonios Antoniadis, Chien-Chung Huang, Sebastian Ott:
A Fully Polynomial-Time Approximation Scheme for Speed Scaling with Sleep State. 1102-1113 - Anamitra Roy Choudhury, Syamantak Das, Naveen Garg
Rejecting jobs to Minimize Load and Maximum Flow-time. 1114-1133 - Maxim Sviridenko, Jan Vondrák, Justin Ward:
Optimal approximation for submodular and supermodular optimization with bounded curvature. 1134-1148 - Niv Buchbinder
Comparing Apples and Oranges: Query Tradeoff in Submodular Maximization. 1149-1168 - T.-H. Hubert Chan, Fei Chen, Shaofeng H.-C. Jiang:
Revealing Optimal Thresholds for Generalized Secretary Problem via Continuous LP: Impacts on Online K-Item Auction and Bipartite K-Matching with Random Arrival Order. 1169-1188 - Moran Feldman
A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem. 1189-1201 - Niv Buchbinder
Online Submodular Maximization with Preemption. 1202-1216 - Hossein Esfandiari, Mohammad Taghi Hajiaghayi, Vahid Liaghat, Morteza Monemizadeh, Krzysztof Onak:
Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond. 1217-1233 - Rajesh Hemant Chitnis
Parameterized Streaming: Maximal Matching and Vertex Cover. 1234-1251 - Timothy Naumovitz, Michael E. Saks:
A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity. 1252-1262 - Michael Kapralov
Streaming Lower Bounds for Approximating MAX-CUT. 1263-1282 - Guy Moshkovitz, Asaf Shapira:
Decomposing a Graph Into Expanding Subgraphs. 1283-1295 - Ran Gelles, Bernhard Haeupler
Capacity of Interactive Communication over Erasure Channels and Channels with Feedback. 1296-1311 - Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang:
Limitations on Testable Affine-Invariant Codes in the High-Rate Regime. 1312-1325 - Badih Ghazi, Euiwoong Lee
LP/SDP Hierarchy Lower Bounds for Decoding Random LDPC Codes. 1326-1342 - Maokai Lin, Patrick Jaillet:
On the Quickest Flow Problem in Dynamic Networks - A Parametric Min-Cost Flow Approach. 1343-1356 - Chidambaram Annamalai, Christos Kalaitzis, Ola Svensson:
Combinatorial Algorithm for Restricted Max-Min Fair Allocation. 1357-1372 - Seeun Umboh
Online Network Design Algorithms via Hierarchical Decompositions. 1373-1387 - Aranyak Mehta, Bo Waggoner, Morteza Zadimoghaddam:
Online Stochastic Matching with Unequal Probabilities. 1388-1404 - Shipra Agrawal, Nikhil R. Devanur:
Fast Algorithms for Online Stochastic Convex Programming. 1405-1424 - János Balogh, József Békési, György Dósa, Jirí Sgall, Rob van Stee:
The optimal absolute ratio for online bin packing. 1425-1438 - Zeyuan Allen Zhu, Lorenzo Orecchia:
Using Optimization to Break the Epsilon Barrier: A Faster and Simpler Width-Independent Algorithm for Solving Positive Linear Programs in Parallel. 1439-1456 - Sayan Bandyapadhyay, Santanu Bhowmick, Kasturi R. Varadarajan:
Approximation Schemes for Partitioning: Convex Decomposition and Surface Approximation. 1457-1470 - Hu Ding, Jinhui Xu:
A Unified Framework for Clustering Constrained Data without Locality Property. 1471-1490 - Anna Adamaszek
A quasi-PTAS for the Two-Dimensional Geometric Knapsack Problem. 1491-1505 - János Pach, Natan Rubin, Gábor Tardos:
On the Richter-Thomassen Conjecture about Pairwise Intersecting Closed Curves. 1506-1516 - Jacob Fox, János Pach, Andrew Suk:
Density and regularity theorems for semi-algebraic hypergraphs. 1517-1530 - Jingcheng Liu, Pinyan Lu
FPTAS for Counting Monotone CNF. 1531-1548 - Alistair Sinclair, Piyush Srivastava, Daniel Stefankovic, Yitong Yin:
Spatial mixing and the connective constant: Optimal bounds. 1549-1563 - Catherine S. Greenhill:
The switch Markov chain for sampling irregular graphs (Extended Abstract). 1564-1572 - Sarah Cannon, Sarah Miracle, Dana Randall:
Phase Transitions in Random Dyadic Tilings and Rectangular Dissections. 1573-1589 - Nisheeth K. Vishnoi:
The Speed of Evolution. 1590-1601 - Greg Aloupis, Luis Barba, Paz Carmi, Vida Dujmovic, Fabrizio Frati
Compatible Connectivity-Augmentation of Planar Disconnected Graphs. 1602-1615 - Sylvester David Eriksson-Bique
Geometric k Shortest Paths. 1616-1625 - Siu-Wing Cheng
Triangulation Refinement and Approximate Shortest Paths in Weighted Regions. 1626-1640 - Luis Barba, Stefan Langerman:
Optimal detection of intersections between convex polyhedra. 1641-1654 - Hsien-Chih Chang, Jeff Erickson, Chao Xu
Detecting Weakly Simple Polygons. 1655-1670 - Virginia Vassilevska Williams, Joshua R. Wang, Richard Ryan Williams
Finding Four-Node Subgraphs in Triangle Time. 1671-1680 - Amir Abboud, Fabrizio Grandoni
Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter. 1681-1697 - Bartosz Walczak
Minors and Dimension. 1698-1707 - Mathew C. Francis, Pavol Hell, Juraj Stacho:
Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm. 1708-1727 - Lino Demasi, Bojan Mohar:
Four terminal planar Delta-Wye reducibility via rooted K2, 4 minors. 1728-1742 - Rajko Nenadov, Nemanja Skoric, Angelika Steger:
An algorithmic framework for obtaining lower bounds for random Ramsey problems extended abstract. 1743-1751 - Asaf Ferber, Rajko Nenadov, Ueli Peter, Andreas Noever, Nemanja Skoric:
Robust hamiltonicity of random directed graphs extended abstract. 1752-1758 - James Norris, Yuval Peres, Alex Zhai:
Surprise probabilities in Markov chains. 1759-1773 - Riddhipratim Basu, Jonathan Hermon, Yuval Peres:
Characterization of cutoff for reversible Markov chains. 1774-1791 - David G. Harris:
Lopsidependency in the Moser-Tardos framework: Beyond the Lopsided Lovász Local Lemma. 1792-1808 - Deeparnab Chakrabarty, Kashyap Dixit, Madhav Jha, C. Seshadhri:
Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties. 1809-1828 - Jayadev Acharya, Constantinos Daskalakis:
Testing Poisson Binomial Distributions. 1829-1840 - Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin
Testing Identity of Structured Distributions. 1841-1854 - Jayadev Acharya, Alon Orlitsky, Ananda Theertha Suresh, Himanshu Tyagi:
The Complexity of Estimating Rényi Entropy. 1855-1869 - Arnab Bhattacharyya, Pooya Hatami, Madhur Tulsiani:
Algorithmic regularity for polynomials and applications. 1870-1889 - Sampath Kannan, Jamie Morgenstern, Aaron Roth
Approximately Stable, School Optimal, and Student-Truthful Many-to-One Matchings (via Differential Privacy). 1890-1903 - Jannik Matuschke, Martin Skutella, José A. Soto:
Robust randomized matchings. 1904-1915 - Yash Kanoria, Daniela Sabán, Jay Sethuraman:
The size of the core in assignment markets. 1916-1924 - Ross Anderson, Itai Ashlagi, David Gamarnik, Yash Kanoria:
A dynamic model of barter exchange. 1925-1933 - Constantinos Daskalakis, S. Matthew Weinberg
Bayesian Truthful Mechanisms for Job Scheduling from Bi-criterion Approximation Algorithms. 1934-1952 - Amin Coja-Oghlan, Uriel Feige, Michael Krivelevich, Daniel Reichman:
Contagious Sets in Expanders. 1953-1987 - Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura, Nikos Parotsidis:
2-Edge Connectivity in Directed Graphs. 1988-2005 - Keren Censor-Hillel, Mohsen Ghaffari, George Giakkoupis, Bernhard Haeupler
Tight Bounds on Vertex Connectivity Under Vertex Sampling. 2006-2018 - Aleksander Madry, Damian Straszak, Jakub Tarnawski:
Fast Generation of Random Spanning Trees and the Effective Resistance Metric. 2019-2036 - Ashish Goel, Sanjeev Khanna, Sharath Raghvendra, Hongyang Zhang:
Connectivity in Random Forests and Credit Networks. 2037-2048
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-15 19:19 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: