default search action
21st RANDOM / 20th APPROX 2017: Berkeley, CA, USA
- Klaus Jansen, José D. P. Rolim, David Williamson, Santosh S. Vempala:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2017, August 16-18, 2017, Berkeley, CA, USA. LIPIcs 81, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2017, ISBN 978-3-95977-044-6 - Frontmatter, Table of Contents, Preface, Organization, External Reviewers, List of Authors. 0:1-0:1
- Itai Ashlagi, Yossi Azar
, Moses Charikar
Min-Cost Bipartite Perfect Matching with Delays. 1:1-1:20 - Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Euiwoong Lee, Chao Xu:
Global and Fixed-Terminal Cuts in Digraphs. 2:1-2:20 - Glencora Borradaile, Baigong Zheng:
A PTAS for Three-Edge-Connected Survivable Network Design in Planar Graphs. 3:1-3:13 - Joshua Brakensiek, Venkatesan Guruswami:
The Quest for Strong Inapproximability Results with Perfect Completeness. 4:1-4:20 - Zachary Friggstad, Arnoosh Golestanian, Kamyar Khodamoradi
Scheduling Problems over Network of Machines. 5:1-5:18 - Michel X. Goemans, Francisco Unda:
Approximating Incremental Combinatorial Optimization Problems. 6:1-6:14 - Anupam Gupta, Archit Karandikar:
Stochastic Unsplittable Flows. 7:1-7:19 - Venkatesan Guruswami, Ameya Velingker, Santhoshini Velusamy
Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph. 8:1-8:19 - Samuel Haney, Bruce M. Maggs, Biswaroop Maiti, Debmalya Panigrahi, Rajmohan Rajaraman, Ravi Sundaram:
Symmetric Interdiction for Matching Problems. 9:1-9:19 - David G. Harris, Thomas W. Pensyl, Aravind Srinivasan, Khoa Trinh:
A Lottery Model for Center-Type Problems with Outliers. 10:1-10:19 - Chien-Chung Huang, Naonori Kakimura, Yuichi Yoshida:
Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint. 11:1-11:14 - Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Jonathan R. Ullman, Ali Vakilian
Fractional Set Cover in the Streaming Model. 12:1-12:20 - Klaus Jansen, Kim-Manuel Klein, Maria Kosche, Leon Ladewig:
Online Strip Packing with Polynomial Migration. 13:1-13:18 - Gorav Jindal
Density Independent Algorithms for Sparsifying k-Step Random Walks. 14:1-14:17 - Sagar Kale
Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams. 15:1-15:21 - Thomas Kesselheim, Andreas Tönnis:
Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints. 16:1-16:22 - Jochen Könemann, Neil Olver, Kanstantsin Pashkovich, R. Ravi, Chaitanya Swamy, Jens Vygen:
On the Integrality Gap of the Prize-Collecting Steiner Forest LP. 17:1-17:13 - Vedat Levi Alev
Approximating Unique Games Using Low Diameter Graph Decomposition. 18:1-18:15 - Edo Liberty, Maxim Sviridenko:
Greedy Minimization of Weakly Supermodular Set Functions. 19:1-19:11 - Maciej Obremski, Maciej Skorski
Renyi Entropy Estimation Revisited. 20:1-20:15 - Yuval Rabani, Rakesh Venkat:
Approximating Sparsest Cut in Low Rank Graphs via Embeddings from Approximately Low Dimensional Spaces. 21:1-21:14 - Tim Roughgarden, Inbal Talgam-Cohen, Jan Vondrák:
When Are Welfare Guarantees Robust?. 22:1-22:23 - Rupam Acharyya, Daniel Stefankovic:
Glauber Dynamics for Ising Model on Convergent Dense Graph Sequences. 23:1-23:22 - Naman Agarwal, Karthekeyan Chandrasekaran, Alexandra Kolla, Vivek Madan:
On the Expansion of Group-Based Lifts. 24:1-24:13 - Noga Alon, Omri Ben-Eliezer:
Efficient Removal Lemmas for Matrices. 25:1-25:18 - Omer Angel
The String of Diamonds Is Tight for Rumor Spreading. 26:1-26:9 - Haim Avron
Sharper Bounds for Regularized Data Fitting. 27:1-27:22 - Jess Banks, Robert Kleinberg, Cristopher Moore:
The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime. 28:1-28:22 - Anna Ben-Hamou, Yuval Peres:
Cutoff for a Stratified Random Walk on the Hypercube. 29:1-29:10 - Arnab Bhattacharyya, Sivakanth Gopi, Avishay Tal:
Lower Bounds for 2-Query LCCs over Large Alphabet. 30:1-30:20 - Vijay Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee:
Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere. 31:1-31:20 - Jaroslaw Blasiok, Jian Ding, Jelani Nelson:
Continuous Monitoring of l_p Norms in Data Streams. 32:1-32:13 - Joshua Brakensiek:
Vertex Isoperimetry and Independent Set Stability for Tensor Powers of Cliques. 33:1-33:15 - Sarah Cannon, David A. Levin, Alexandre Stauffer:
Polynomial Mixing of the Edge-Flip Markov Chain for Unbiased Dyadic Tilings. 34:1-34:21 - Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova:
Agnostic Learning from Tolerant Natural Proofs. 35:1-35:19 - L. Elisa Celis, Amit Deshpande, Tarun Kathuria, Damian Straszak, Nisheeth K. Vishnoi:
On the Complexity of Constrained Determinantal Point Processes. 36:1-36:22 - Xi Chen, Adam Freilich, Rocco A. Servedio, Timothy Sun:
Sample-Based High-Dimensional Convexity Testing. 37:1-37:20 - Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten:
Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces. 38:1-38:21 - Alessandro Chiesa, Peter Manohar, Igor Shinkar:
On Axis-Parallel Tests for Tensor Product Codes. 39:1-39:22 - Amin Coja-Oghlan, Charilaos Efthymiou, Nor Jaafari, Mihyun Kang, Tobias Kapetanopoulos:
Charting the Replica Symmetric Phase. 40:1-40:17 - Dean Doron
Probabilistic Logarithmic-Space Algorithms for Laplacian Solvers. 41:1-41:20 - Funda Ergün, Elena Grigorescu, Erfan Sadeqi Azer, Samson Zhou:
Streaming Periodicity with Mismatches. 42:1-42:21 - S. Luna Frank-Fischer, Venkatesan Guruswami, Mary Wootters:
Locality via Partially Lifted Codes. 43:1-43:17 - Cody R. Freitag, Eric Price, William J. Swartworth:
Testing Hereditary Properties of Sequences. 44:1-44:10 - Alan M. Frieze, Wesley Pegden:
Traveling in Randomly Embedded Random Graphs. 45:1-45:17 - Alexander Golovnev, Oded Regev, Omri Weinstein:
The Minrank of Random Graphs. 46:1-46:13 - Venkatesan Guruswami, Ray Li:
Efficiently Decodable Codes for the Binary Deletion Channel. 47:1-47:13 - Ilya Volkovich:
On Some Computations on Sparse Polynomials. 48:1-48:21 - Thomas Watson:
Communication Complexity of Statistical Distance. 49:1-49:10
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-12-26 00:59 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: