default search action
18th RANDOM / 17th APPROX 2014: Barcelona, Spain
- Klaus Jansen, José D. P. Rolim, Nikhil R. Devanur, Cristopher Moore:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014, September 4-6, 2014, Barcelona, Spain. LIPIcs 28, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2014, ISBN 978-3-939897-74-3
Papers
- Frontmatter, Table of Contents, Preface, Conference Organization. i-xviii
- Ittai Abraham, Shiri Chechik, Kunal Talwar:
Fully Dynamic All-Pairs Shortest Paths: Breaking the O(n) Barrier. 1-16 - Sara Ahmadian, Babak Behsaz, Zachary Friggstad, Amin Jorati, Mohammad R. Salavatipour, Chaitanya Swamy:
Approximation Algorithms for Minimum-Load k-Facility Location. 17-33 - Noga Alon, Troy Lee, Adi Shraibman:
The Cover Number of a Matrix and its Algorithmic Applications. 34-47 - Siddharth Barman, Shuchi Chawla, Seeun Umboh
:
Network Design with Coverage Costs. 48-63 - Kshipra Bhawalkar, Sreenivas Gollapudi, Debmalya Panigrahi:
Online Set Cover with Set Requests. 64-79 - Eden Chlamtác, Michael Dinitz
Lowest Degree k-Spanner: Approximation and Hardness. 80-95 - Michael S. Crouch
Improved Streaming Algorithms for Weighted Matching, via Unweighted Matching. 96-104 - Amit Deshpande, Rakesh Venkat
Guruswami-Sinop Rounding without Higher Level Lasserre. 105-114 - Michael Dinitz
Improved Approximation Algorithm for Steiner k-Forest with Nearly Uniform Weights. 115-127 - Adrian Dumitrescu, Minghui Jiang, Csaba D. Tóth:
Computing Opaque Interior Barriers à la Shermer. 128-143 - Alina Ene, Jan Vondrák:
Hardness of Submodular Cost Allocation: Lattice Matching and a Simplex Coloring Conjecture. 144-159 - Moran Feldman
Constrained Monotone Function Maximization and the Supermodular Degree. 160-175 - Andreas Emil Feldmann
On the Equivalence of the Bidirected and Hypergraphic Relaxations for Steiner Tree. 176-191 - Michal Feldman, Nicole Immorlica, Brendan Lucier, S. Matthew Weinberg
Reaching Consensus via Non-Bayesian Asynchronous Learning in Social Networks. 192-208 - Takuro Fukunaga
Deliver or hold: Approximation Algorithms for the Periodic Inventory Routing Problem. 209-225 - Martin Gairing, Tobias Harks, Max Klimm:
Complexity and Approximation of the Continuous Network Design Problem. 226-241 - Christoph Hansknecht, Max Klimm, Alexander Skopalik:
Approximate Pure Nash Equilibria in Weighted Congestion Games. 242-257 - Nicholas J. A. Harvey, Roy Schwartz, Mohit Singh:
Discrepancy Without Partial Colorings. 258-273 - Shlomo Jozeph:
Universal Factor Graphs for Every NP-Hard Boolean CSP. 274-283 - Jeremy Karp, R. Ravi:
A 9/7 -Approximation Algorithm for Graphic TSP in Cubic Bipartite Graphs. 284-296 - Stavros G. Kolliopoulos, Yannis Moysoglou:
Sherali-Adams Gaps, Flow-cover Inequalities and Generalized Configurations for Capacity-constrained Facility Location. 297-312 - Tsz Chiu Kwok, Lap Chi Lau:
Lower Bounds on Expansions of Graph Powers. 313-324 - Shanfei Li:
An Improved Approximation Algorithm for the Hard Uniform Capacitated k-median Problem. 325-338 - Anand Louis, Yury Makarychev:
Approximation Algorithms for Hypergraph Small Set Expansion and Small Set Vertex Expansion. 339-355 - Shashi Mittal, Andreas S. Schulz, Sebastian Stiller:
Robust Appointment Scheduling. 356-370 - Abhiram Natarajan, Yi Wu:
Computational Complexity of Certifying Restricted Isometry Property. 371-380 - Prasad Raghavendra, Tselil Schramm
Gap Amplification for Small-Set Expansion via Random Walks. 381-391 - Alan J. Soper, Vitaly A. Strusevich:
Power of Preemption on Uniform Parallel Machines. 392-402 - Chaitanya Swamy:
Improved Approximation Algorithms for Matroid and Knapsack Median Problems and Applications. 403-418 - Suguru Tamaki, Yuichi Yoshida:
Robust Approximation of Temporal CSP. 419-432 - Cenny Wenner:
Parity is Positively Useless. 433-448 - Victor Bapst, Amin Coja-Oghlan, Samuel Hetterich, Felicia Raßmann, Dan Vilenchik:
The Condensation Phase Transition in Random Graph Coloring. 449-464 - Eric Blais, Joshua Brody, Badih Ghazi:
The Information Complexity of Hamming Distance. 465-489 - Julia Böttcher
An Approximate Version of the Tree Packing Conjecture via Random Embeddings. 490-499 - Milan Bradonjic, Will Perkins
On Sharp Thresholds in Random Geometric Graphs. 500-514 - Gábor Braun, Samuel Fiorini, Sebastian Pokutta:
Average Case Polyhedral Complexity of the Maximum Stable Set Problem. 515-530 - Vladimir Braverman, Jonathan Katzman, Charles Seidell, Gregory Vorsanger:
An Optimal Algorithm for Large Frequency Moments Using O(n^(1-2/k)) Bits. 531-544 - Joshua Brody, Amit Chakrabarti
Certifying Equality With Limited Interaction. 545-581 - Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Stefankovic
#BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Non-uniqueness Region. 582-595 - Arkadev Chattopadhyay, Michael E. Saks:
The Power of Super-logarithmic Number of Players. 596-603 - Flavio Chierichetti, Anirban Dasgupta
On Reconstructing a Hidden Permutation. 604-617 - Gil Cohen, Anat Ganor, Ran Raz
Two Sides of the Coin Problem. 618-629 - Josep Díaz, Leslie Ann Goldberg, David Richerby
Absorption Time of the Moran Process. 630-642 - Chandan K. Dubey, Thomas Holenstein:
Sampling a Uniform Solution of a Quadratic Equation Modulo a Prime Power. 643-653 - Nathanaël François, Rahul Jain
Unidirectional Input/Output Streaming Complexity of Reversal and Sorting. 654-668 - Hu Fu, Robert D. Kleinberg:
Improved Lower Bounds for Testing Triangle-freeness in Boolean Functions via Fast Matrix Multiplication. 669-676 - Andreas Galanis, Daniel Stefankovic
Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results. 677-691 - Anat Ganor, Ran Raz
Space Pseudorandom Generators by Communication Complexity Lower Bounds. 692-703 - Oded Goldreich
On Multiple Input Problems in Property Testing. 704-720 - Mika Göös, Thomas Watson:
Communication Complexity of Set-Disjointness for All Probabilities. 721-736 - Alan Guo, Madhu Sudan:
List Decoding Group Homomorphisms Between Supersolvable Groups. 737-747 - Venkatesan Guruswami, Carol Wang:
Evading Subspaces Over Large Fields and Explicit List-decodable Rank-metric Codes. 748-761 - T. S. Jayram, Jan Vondrák:
Exchangeability and Realizability: De Finetti Theorems on Graphs. 762-778 - Varun Kanade
Global and Local Information in Clustering Labeled Block Models. 779-792 - Adam R. Klivans, Pravesh Kothari:
Embedding Hard Learning Problems Into Gaussian Space. 793-809 - Michael Krivelevich, Daniel Reichman, Wojciech Samotij:
Smoothed Analysis on Connected Graphs. 810-825 - Reut Levi, Dana Ron
Local Algorithms for Sparse Spanning Graphs. 826-842 - Jingcheng Liu, Pinyan Lu
The Complexity of Ferromagnetic Two-spin Systems with External Fields. 843-856 - Abbas Mehrabian, Nick Wormald:
It's a Small World for Random Surfers. 857-871 - Raghu Meka, Omer Reingold, Yuan Zhou:
Deterministic Coupon Collection and Better Strong Dispersers. 872-884 - Thomas Steinke, Salil P. Vadhan, Andrew Wan:
Pseudorandomness and Fourier Growth Bounds for Width-3 Branching Programs. 885-899
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-13 18: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: