APPROX/RANDOM 2015 August 24–26, 2015 - Princeton, USA

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)



Naveen Garg and Klaus Jansen and Anup Rao and José D. P. Rolim (Eds.)
ISBN 978-3-939897-89-7, LIPICS Vol. 40 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 29 MB)
Search Publication Server


Authors
  • Štefankovic, Daniel
  • Abed, Fidaa
  • Abraham, Ittai
  • Acharya, Jayadev
  • Adamaszek, Anna
  • Adjiashvili, David
  • Anbalagan, Yogesh
  • Bansal, Nikhil
  • Bapst, Victor
  • Barak, Boaz
  • Bauer, Balthazar
  • Baveja, Alok
  • Berndt, Sebastian
  • Bhangale, Amey
  • Bhattiprolu, Vijay V. S. P.
  • Blais, Eric
  • Blanca, Antonio
  • Bottesch, Ralph Christian
  • Braverman, Vladimir
  • Brody, Joshua
  • Bun, Mark
  • Canonne, Clément L.
  • Carmosino, Marco L.
  • Chalermsook, Parinya
  • Chavan, Amit
  • Chechik, Shiri
  • Chen, Lin
  • Chestnut, Stephen R.
  • Chuzhoy, Julia
  • Cloostermans, Bouke
  • Cohen, Edith
  • Cohen, Gil
  • Coja-Oghlan, Amin
  • Cooley, Oliver
  • Correa, José
  • Cygan, Marek
  • Dinitz, Michael
  • Drudi, Zachary
  • Efthymiou, Charilaos
  • Elkin, Michael
  • Felber, David
  • Fichtenberger, Hendrik
  • Filtser, Arnold
  • Forbes, Michael A.
  • Friggstad, Zachary
  • Galanis, Andreas
  • Gao, Zhihan
  • Garg, Naveen
  • Gavinsky, Dmitry
  • Ge, Rong
  • Guo, Siyao
  • Gupta, Anupam
  • Guruswami, Venkatesan
  • Håstad, Johan
  • Haeupler, Bernhard
  • Harris, David G.
  • Harvey, Nicholas J. A.
  • Huang, Chien-Chung
  • Huang, Hao
  • Huang, Sangxia
  • Iglesias, Jennifer
  • Impagliazzo, Russell
  • Ingram, Stephen
  • Iwama, Kazuo
  • Jaafari, Nor
  • Jansen, Klaus
  • Kabanets, Valentine
  • Kamath, Gautam
  • Kamath, Pritish
  • Kang, Mihyun
  • Kaplan, Haim
  • Karrenbauer, Andreas
  • Kasiviswanathan, Shiva Prasad
  • Kim, David H. K.
  • Klauck, Hartmut
  • Klein, Kim-Manuel
  • Kociumaka, Tomasz
  • Kolokolova, Antonina
  • Komargodski, Ilan
  • Kothari, Robin
  • Krauthgamer, Robert
  • Krishnaswamy, Ravishankar
  • Lee, Euiwoong
  • Lovett, Shachar
  • Ma, Tengyu
  • Manokaran, Rajsekar
  • Manurangsi, Pasin
  • Megow, Nicole
  • Miyazaki, Shuichi
  • Moitra, Ankur
  • Moran, Shay
  • Moshkovitz, Dana
  • Mossel, Elchanan
  • Nagarajan, Viswanath
  • Neiman, Ofer
  • Nikiforov, Andrei
  • Norin, Sergey
  • O’Donnell, Ryan
  • Oliveira, Igor C.
  • Ostrovsky, Rafail
  • Pérez-Lantero, Pablo
  • Peng, Pan
  • Pruhs, Kirk
  • Racicot-Desloges, David
  • Raghavendra, Prasad
  • Rajaraman, Rajmohan
  • Rao, Anup
  • Ravi, R.
  • Regev, Oded
  • Rischke, Roman
  • Roch, Sebastien
  • Rolim, José D. P.
  • Roytman, Alan
  • Rudelson, Mark
  • Sanchez, Mario
  • Santha, Miklos
  • Saptharishi, Ramprasad
  • Sarpatwar, Kanthi K.
  • Schewior, Kevin
  • Schieber, Baruch
  • Servedio, Rocco A.
  • Shachnai, Hadas
  • Sinclair, Alistair
  • Skubch, Kathrin
  • Sohler, Christian
  • Soto, José A.
  • Srinivasan, Aravind
  • Stein, Cliff
  • Steinke, Thomas
  • Steurer, David
  • Stougie, Leen
  • Sullivan, Francis
  • Sun, Xiaoming
  • Sundaram, Ravi
  • Tal, Avishay
  • Tan, Li-Yang
  • Trevisan, Luca
  • Varma, Girish
  • Velingker, Ameya
  • Venkat, Rakesh
  • Vetta, Adrian
  • Vigoda, Eric
  • Vijayaraghavan, Aravindan
  • Volkovich, Ilya
  • Wagner, Tal
  • Wang, Carol
  • Warfield, Andrew
  • Wieder, Udi
  • Wiese, Andreas
  • Wires, Jake
  • Witmer, David
  • Wolf, Joel L.
  • Woodruff, David P.
  • Wright, John
  • Wu, Hehui
  • Xu, Pan
  • Yanagisawa, Hiroki
  • Yehudayoff, Amir

  •   
    Frontmatter, Table of Contents, Preface, Program Commitees, External Reviewers, List of Authors
    Authors: Garg, Naveen ; Jansen, Klaus ; Rao, Anup ; Rolim, José D. P.

    Abstract | Document (353 KB) | BibTeX

    On Guillotine Cutting Sequences
    Authors: Abed, Fidaa ; Chalermsook, Parinya ; Correa, José ; Karrenbauer, Andreas ; Pérez-Lantero, Pablo ; Soto, José A. ; Wiese, Andreas

    Abstract | Document (545 KB) | BibTeX

    Approximate Nearest Neighbor Search in Metrics of Planar Graphs
    Authors: Abraham, Ittai ; Chechik, Shiri ; Krauthgamer, Robert ; Wieder, Udi

    Abstract | Document (687 KB) | BibTeX

    How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking
    Authors: Adamaszek, Anna ; Chalermsook, Parinya ; Wiese, Andreas

    Abstract | Document (584 KB) | BibTeX

    Non-Uniform Robust Network Design in Planar Graphs
    Authors: Adjiashvili, David

    Abstract | Document (486 KB) | BibTeX

    Large Supports are Required for Well-Supported Nash Equilibria
    Authors: Anbalagan, Yogesh ; Huang, Hao ; Lovett, Shachar ; Norin, Sergey ; Vetta, Adrian ; Wu, Hehui

    Abstract | Document (441 KB) | BibTeX

    Minimizing Maximum Flow-time on Related Machines
    Authors: Bansal, Nikhil ; Cloostermans, Bouke

    Abstract | Document (427 KB) | BibTeX

    A 2-Competitive Algorithm For Online Convex Optimization With Switching Costs
    Authors: Bansal, Nikhil ; Gupta, Anupam ; Krishnaswamy, Ravishankar ; Pruhs, Kirk ; Schewior, Kevin ; Stein, Cliff

    Abstract | Document (500 KB) | BibTeX

    Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree
    Authors: Barak, Boaz ; Moitra, Ankur ; O’Donnell, Ryan ; Raghavendra, Prasad ; Regev, Oded ; Steurer, David ; Trevisan, Luca ; Vijayaraghavan, Aravindan ; Witmer, David ; Wright, John

    Abstract | Document (520 KB) | BibTeX

    Improved Bounds in Stochastic Matching and Optimization
    Authors: Baveja, Alok ; Chavan, Amit ; Nikiforov, Andrei ; Srinivasan, Aravind ; Xu, Pan

    Abstract | Document (483 KB) | BibTeX

    Fully Dynamic Bin Packing Revisited
    Authors: Berndt, Sebastian ; Jansen, Klaus ; Klein, Kim-Manuel

    Abstract | Document (638 KB) | BibTeX

    Approximate Hypergraph Coloring under Low-discrepancy and Related Promises
    Authors: Bhattiprolu, Vijay V. S. P. ; Guruswami, Venkatesan ; Lee, Euiwoong

    Abstract | Document (596 KB) | BibTeX

    Stochastic and Robust Scheduling in the Cloud
    Authors: Chen, Lin ; Megow, Nicole ; Rischke, Roman ; Stougie, Leen

    Abstract | Document (491 KB) | BibTeX

    On Approximating Node-Disjoint Paths in Grids
    Authors: Chuzhoy, Julia ; Kim, David H. K.

    Abstract | Document (1,778 KB) | BibTeX

    Approximating Upper Degree-Constrained Partial Orientations
    Authors: Cygan, Marek ; Kociumaka, Tomasz

    Abstract | Document (478 KB) | BibTeX

    Approximating Hit Rate Curves using Streaming Algorithms
    Authors: Drudi, Zachary ; Harvey, Nicholas J. A. ; Ingram, Stephen ; Warfield, Andrew ; Wires, Jake

    Abstract | Document (538 KB) | BibTeX

    Terminal Embeddings
    Authors: Elkin, Michael ; Filtser, Arnold ; Neiman, Ofer

    Abstract | Document (638 KB) | BibTeX

    On Linear Programming Relaxations for Unsplittable Flow in Trees
    Authors: Friggstad, Zachary ; Gao, Zhihan

    Abstract | Document (562 KB) | BibTeX

    Inapproximability of H-Transversal/Packing
    Authors: Guruswami, Venkatesan ; Lee, Euiwoong

    Abstract | Document (707 KB) | BibTeX

    Towards a Characterization of Approximation Resistance for Symmetric CSPs
    Authors: Guruswami, Venkatesan ; Lee, Euiwoong

    Abstract | Document (550 KB) | BibTeX

    Sequential Importance Sampling Algorithms for Estimating the All-Terminal Reliability Polynomial of Sparse Graphs
    Authors: Harris, David G. ; Sullivan, Francis

    Abstract | Document (482 KB) | BibTeX

    Improved NP-Inapproximability for 2-Variable Linear Equations
    Authors: Håstad, Johan ; Huang, Sangxia ; Manokaran, Rajsekar ; O’Donnell, Ryan ; Wright, John

    Abstract | Document (567 KB) | BibTeX

    A Tight Approximation Bound for the Stable Marriage Problem with Restricted Ties
    Authors: Huang, Chien-Chung ; Iwama, Kazuo ; Miyazaki, Shuichi ; Yanagisawa, Hiroki

    Abstract | Document (545 KB) | BibTeX

    Designing Overlapping Networks for Publish-Subscribe Systems
    Authors: Iglesias, Jennifer ; Rajaraman, Rajmohan ; Ravi, R. ; Sundaram, Ravi

    Abstract | Document (525 KB) | BibTeX

    Approximating Dense Max 2-CSPs
    Authors: Manurangsi, Pasin ; Moshkovitz, Dana

    Abstract | Document (530 KB) | BibTeX

    The Container Selection Problem
    Authors: Nagarajan, Viswanath ; Sarpatwar, Kanthi K. ; Schieber, Baruch ; Shachnai, Hadas ; Wolf, Joel L.

    Abstract | Document (668 KB) | BibTeX

    Tight Bounds for Graph Problems in Insertion Streams
    Authors: Sun, Xiaoming ; Woodruff, David P.

    Abstract | Document (475 KB) | BibTeX

    A Chasm Between Identity and Equivalence Testing with Conditional Queries
    Authors: Acharya, Jayadev ; Canonne, Clément L. ; Kamath, Gautam

    Abstract | Document (617 KB) | BibTeX

    Harnessing the Bethe Free Energy
    Authors: Bapst, Victor ; Coja-Oghlan, Amin

    Abstract | Document (553 KB) | BibTeX

    Internal Compression of Protocols to Entropy
    Authors: Bauer, Balthazar ; Moran, Shay ; Yehudayoff, Amir

    Abstract | Document (491 KB) | BibTeX

    On Fortification of Projection Games
    Authors: Bhangale, Amey ; Saptharishi, Ramprasad ; Varma, Girish ; Venkat, Rakesh

    Abstract | Document (539 KB) | BibTeX

    Learning Circuits with few Negations
    Authors: Blais, Eric ; Canonne, Clément L. ; Oliveira, Igor C. ; Servedio, Rocco A. ; Tan, Li-Yang

    Abstract | Document (547 KB) | BibTeX

    Dynamics for the Mean-field Random-cluster Model
    Authors: Blanca, Antonio ; Sinclair, Alistair

    Abstract | Document (586 KB) | BibTeX

    Correlation in Hard Distributions in Communication Complexity
    Authors: Bottesch, Ralph Christian ; Gavinsky, Dmitry ; Klauck, Hartmut

    Abstract | Document (614 KB) | BibTeX

    Zero-One Laws for Sliding Windows and Universal Sketches
    Authors: Braverman, Vladimir ; Ostrovsky, Rafail ; Roytman, Alan

    Abstract | Document (568 KB) | BibTeX

    Universal Sketches for the Frequency Negative Moments and Other Decreasing Streaming Sums
    Authors: Braverman, Vladimir ; Chestnut, Stephen R.

    Abstract | Document (539 KB) | BibTeX

    Dependent Random Graphs and Multi-Party Pointer Jumping
    Authors: Brody, Joshua ; Sanchez, Mario

    Abstract | Document (576 KB) | BibTeX

    Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness
    Authors: Bun, Mark ; Steinke, Thomas

    Abstract | Document (542 KB) | BibTeX

    Tighter Connections between Derandomization and Circuit Lower Bounds
    Authors: Carmosino, Marco L. ; Impagliazzo, Russell ; Kabanets, Valentine ; Kolokolova, Antonina

    Abstract | Document (535 KB) | BibTeX

    Average Distance Queries through Weighted Samples in Graphs and Metric Spaces: High Scalability with Tight Statistical Guarantees
    Authors: Chechik, Shiri ; Cohen, Edith ; Kaplan, Haim

    Abstract | Document (582 KB) | BibTeX

    Two Structural Results for Low Degree Polynomials and Applications
    Authors: Cohen, Gil ; Tal, Avishay

    Abstract | Document (634 KB) | BibTeX

    The Minimum Bisection in the Planted Bisection Model
    Authors: Coja-Oghlan, Amin ; Cooley, Oliver ; Kang, Mihyun ; Skubch, Kathrin

    Abstract | Document (510 KB) | BibTeX

    Local Convergence of Random Graph Colorings
    Authors: Coja-Oghlan, Amin ; Efthymiou, Charilaos ; Jaafari, Nor

    Abstract | Document (482 KB) | BibTeX

    Towards Resistance Sparsifiers
    Authors: Dinitz, Michael ; Krauthgamer, Robert ; Wagner, Tal

    Abstract | Document (538 KB) | BibTeX

    Reconstruction/Non-reconstruction Thresholds for Colourings of General Galton-Watson Trees
    Authors: Efthymiou, Charilaos

    Abstract | Document (518 KB) | BibTeX

    A Randomized Online Quantile Summary in O(1/epsilon * log(1/epsilon)) Words
    Authors: Felber, David ; Ostrovsky, Rafail

    Abstract | Document (515 KB) | BibTeX

    On Constant-Size Graphs That Preserve the Local Structure of High-Girth Graphs
    Authors: Fichtenberger, Hendrik ; Peng, Pan ; Sohler, Christian

    Abstract | Document (524 KB) | BibTeX

    Dimension Expanders via Rank Condensers
    Authors: Forbes, Michael A. ; Guruswami, Venkatesan

    Abstract | Document (530 KB) | BibTeX

    Swendsen-Wang Algorithm on the Mean-Field Potts Model
    Authors: Galanis, Andreas ; Štefankovic, Daniel ; Vigoda, Eric

    Abstract | Document (610 KB) | BibTeX

    Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithms
    Authors: Ge, Rong ; Ma, Tengyu

    Abstract | Document (518 KB) | BibTeX

    Negation-Limited Formulas
    Authors: Guo, Siyao ; Komargodski, Ilan

    Abstract | Document (579 KB) | BibTeX

    Deletion Codes in the High-noise and High-rate Regimes
    Authors: Guruswami, Venkatesan ; Wang, Carol

    Abstract | Document (446 KB) | BibTeX

    Communication with Partial Noiseless Feedback
    Authors: Haeupler, Bernhard ; Kamath, Pritish ; Velingker, Ameya

    Abstract | Document (519 KB) | BibTeX

    Spectral Norm of Random Kernel Matrices with Applications to Privacy
    Authors: Kasiviswanathan, Shiva Prasad ; Rudelson, Mark

    Abstract | Document (597 KB) | BibTeX

    Separating Decision Tree Complexity from Subcube Partition Complexity
    Authors: Kothari, Robin ; Racicot-Desloges, David ; Santha, Miklos

    Abstract | Document (516 KB) | BibTeX

    Distance-based Species Tree Estimation: Information-Theoretic Trade-off between Number of Loci and Sequence Length under the Coalescent
    Authors: Mossel, Elchanan ; Roch, Sebastien

    Abstract | Document (1,781 KB) | BibTeX

    Deterministically Factoring Sparse Polynomials into Multilinear Factors and Sums of Univariate Polynomials
    Authors: Volkovich, Ilya

    Abstract | Document (533 KB) | BibTeX

      




    DROPS-Home | Fulltext Search | Imprint Published by LZI