default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID19th RANDOM / 18th APPROX 2015: Princeton, NJ, USA
- Naveen Garg, Klaus Jansen, Anup Rao, José D. P. Rolim:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2015, Princeton, NJ, USA, August 24-26, 2015. LIPIcs 40, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2015, ISBN 978-3-939897-89-7 - Frontmatter, Table of Contents, Preface, Program Commitees, External Reviewers, List of Authors. i-xviii
- Fidaa Abed
, Parinya Chalermsook, José Correa, Andreas Karrenbauer, Pablo Pérez-Lantero, José A. Soto, Andreas Wiese:
On Guillotine Cutting Sequences. 1-19 - Ittai Abraham, Shiri Chechik, Robert Krauthgamer, Udi Wieder:
Approximate Nearest Neighbor Search in Metrics of Planar Graphs. 20-42 - Anna Adamaszek, Parinya Chalermsook, Andreas Wiese:
How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking. 43-60 - David Adjiashvili:
Non-Uniform Robust Network Design in Planar Graphs. 61-77 - Yogesh Anbalagan, Hao Huang, Shachar Lovett, Sergey Norin, Adrian Vetta, Hehui Wu:
Large Supports are Required for Well-Supported Nash Equilibria. 78-84 - Nikhil Bansal, Bouke Cloostermans:
Minimizing Maximum Flow-time on Related Machines. 85-95 - Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy, Kirk Pruhs, Kevin Schewior, Clifford Stein:
A 2-Competitive Algorithm For Online Convex Optimization With Switching Costs. 96-109 - Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright:
Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree. 110-123 - Alok Baveja, Amit Chavan, Andrei Nikiforov, Aravind Srinivasan, Pan Xu:
Improved Bounds in Stochastic Matching and Optimization. 124-134 - Sebastian Berndt, Klaus Jansen, Kim-Manuel Klein:
Fully Dynamic Bin Packing Revisited . 135-151 - Vijay V. S. P. Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee:
Approximate Hypergraph Coloring under Low-discrepancy and Related Promises. 152-174 - Lin Chen, Nicole Megow, Roman Rischke, Leen Stougie:
Stochastic and Robust Scheduling in the Cloud. 175-186 - Julia Chuzhoy, David H. K. Kim:
On Approximating Node-Disjoint Paths in Grids. 187-211 - Marek Cygan, Tomasz Kociumaka:
Approximating Upper Degree-Constrained Partial Orientations. 212-224 - Zachary Drudi, Nicholas J. A. Harvey, Stephen Ingram, Andrew Warfield, Jake Wires:
Approximating Hit Rate Curves using Streaming Algorithms. 225-241 - Michael Elkin, Arnold Filtser, Ofer Neiman:
Terminal Embeddings. 242-264 - Zachary Friggstad, Zhihan Gao:
On Linear Programming Relaxations for Unsplittable Flow in Trees. 265-283 - Venkatesan Guruswami, Euiwoong Lee:
Inapproximability of H-Transversal/Packing. 284-304 - Venkatesan Guruswami, Euiwoong Lee:
Towards a Characterization of Approximation Resistance for Symmetric CSPs. 305-322 - David G. Harris, Francis Sullivan:
Sequential Importance Sampling Algorithms for Estimating the All-Terminal Reliability Polynomial of Sparse Graphs. 323-340 - Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, John Wright:
Improved NP-Inapproximability for 2-Variable Linear Equations. 341-360 - Chien-Chung Huang, Kazuo Iwama, Shuichi Miyazaki, Hiroki Yanagisawa:
A Tight Approximation Bound for the Stable Marriage Problem with Restricted Ties. 361-380 - Jennifer Iglesias, Rajmohan Rajaraman, R. Ravi, Ravi Sundaram:
Designing Overlapping Networks for Publish-Subscribe Systems. 381-395 - Pasin Manurangsi, Dana Moshkovitz:
Approximating Dense Max 2-CSPs. 396-415 - Viswanath Nagarajan, Kanthi K. Sarpatwar, Baruch Schieber, Hadas Shachnai, Joel L. Wolf:
The Container Selection Problem. 416-434 - Xiaoming Sun, David P. Woodruff:
Tight Bounds for Graph Problems in Insertion Streams. 435-448 - Jayadev Acharya, Clément L. Canonne, Gautam Kamath:
A Chasm Between Identity and Equivalence Testing with Conditional Queries. 449-466 - Victor Bapst, Amin Coja-Oghlan:
Harnessing the Bethe Free Energy. 467-480 - Balthazar Bauer, Shay Moran, Amir Yehudayoff:
Internal Compression of Protocols to Entropy. 481-496 - Amey Bhangale, Ramprasad Saptharishi, Girish Varma, Rakesh Venkat:
On Fortification of Projection Games. 497-511 - Eric Blais, Clément L. Canonne, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan:
Learning Circuits with few Negations. 512-527 - Antonio Blanca, Alistair Sinclair:
Dynamics for the Mean-field Random-cluster Model. 528-543 - Ralph Bottesch, Dmitry Gavinsky, Hartmut Klauck:
Correlation in Hard Distributions in Communication Complexity. 544-572 - Vladimir Braverman, Rafail Ostrovsky, Alan Roytman:
Zero-One Laws for Sliding Windows and Universal Sketches. 573-590 - Vladimir Braverman, Stephen R. Chestnut:
Universal Sketches for the Frequency Negative Moments and Other Decreasing Streaming Sums. 591-605 - Joshua Brody, Mario Sánchez:
Dependent Random Graphs and Multi-Party Pointer Jumping. 606-624 - Mark Bun, Thomas Steinke:
Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness. 625-644 - Marco Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova:
Tighter Connections between Derandomization and Circuit Lower Bounds. 645-658 - Shiri Chechik, Edith Cohen, Haim Kaplan:
Average Distance Queries through Weighted Samples in Graphs and Metric Spaces: High Scalability with Tight Statistical Guarantees. 659-679 - Gil Cohen, Avishay Tal:
Two Structural Results for Low Degree Polynomials and Applications. 680-709 - Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, Kathrin Skubch:
The Minimum Bisection in the Planted Bisection Model. 710-725 - Amin Coja-Oghlan, Charilaos Efthymiou, Nor Jaafari:
Local Convergence of Random Graph Colorings. 726-737 - Michael Dinitz, Robert Krauthgamer, Tal Wagner:
Towards Resistance Sparsifiers. 738-755 - Charilaos Efthymiou:
Reconstruction/Non-reconstruction Thresholds for Colourings of General Galton-Watson Trees. 756-774 - David Felber, Rafail Ostrovsky:
A Randomized Online Quantile Summary in O(1/epsilon * log(1/epsilon)) Words. 775-785 - Hendrik Fichtenberger, Pan Peng, Christian Sohler:
On Constant-Size Graphs That Preserve the Local Structure of High-Girth Graphs. 786-799 - Michael A. Forbes, Venkatesan Guruswami:
Dimension Expanders via Rank Condensers. 800-814 - Andreas Galanis, Daniel Stefankovic, Eric Vigoda:
Swendsen-Wang Algorithm on the Mean-Field Potts Model. 815-828 - Rong Ge, Tengyu Ma:
Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithms. 829-849 - Siyao Guo, Ilan Komargodski:
Negation-Limited Formulas. 850-866 - Venkatesan Guruswami, Carol Wang:
Deletion Codes in the High-noise and High-rate Regimes. 867-880 - Bernhard Haeupler, Pritish Kamath, Ameya Velingker:
Communication with Partial Noiseless Feedback. 881-897 - Shiva Prasad Kasiviswanathan, Mark Rudelson:
Spectral Norm of Random Kernel Matrices with Applications to Privacy. 898-914 - Robin Kothari, David Racicot-Desloges, Miklos Santha:
Separating Decision Tree Complexity from Subcube Partition Complexity. 915-930 - Elchanan Mossel, Sébastien Roch:
Distance-based Species Tree Estimation: Information-Theoretic Trade-off between Number of Loci and Sequence Length under the Coalescent. 931-942 - Ilya Volkovich:
Deterministically Factoring Sparse Polynomials into Multilinear Factors and Sums of Univariate Polynomials. 943-958
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 2026-01-05 23: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:
