APPROX/RANDOM 2014 September 4-6, 2014 - Barcelona, Spain

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



Klaus Jansen and José D. P. Rolim and Nikhil R. Devanur and Cristopher Moore (Eds.)
ISBN 978-3-939897-74-3, LIPICS Vol. 28 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 27 MB)
Search Publication Server

Authors
  • Abraham, Ittai
  • Ahmadian, Sara
  • Alon, Noga
  • Bapst, Victor
  • Barman, Siddharth
  • Behsaz, Babak
  • Bhawalkar, Kshipra
  • Blais, Eric
  • Bradonjic, Milan
  • Braun, Gábor
  • Braverman, Vladimir
  • Brody, Joshua
  • Böttcher, Julia
  • Cai, Jin-Yi
  • Chakrabarti, Amit
  • Chattopadhyay, Arkadev
  • Chawla, Shuchi
  • Chechik, Shiri
  • Chierichetti, Flavio
  • Chlamtác, Eden
  • Cohen, Gil
  • Coja-Oghlan, Amin
  • Crouch, Michael
  • Dasgupta, Anirban
  • Deshpande, Amit
  • Devanur, Nikhil R.
  • Dinitz, Michael
  • Dubey, Chandan
  • Dumitrescu, Adrian
  • Díaz, Josep
  • Ene, Alina
  • Feldman, Michal
  • Feldman, Moran
  • Feldmann, Andreas Emil
  • Fiorini, Samuel
  • François, Nathanaël
  • Friggstad, Zachary
  • Fu, Hu
  • Fukunaga, Takuro
  • Gairing, Martin
  • Galanis, Andreas
  • Ganor, Anat
  • Ghazi, Badih
  • Goldberg, Leslie Ann
  • Goldreich, Oded
  • Gollapudi, Sreenivas
  • Guo, Alan
  • Guo, Heng
  • Guruswami, Venkatesan
  • Göös, Mika
  • Hansknecht, Christoph
  • Harks, Tobias
  • Harvey, Nicholas J. A.
  • Hetterich, Samuel
  • Hladký, Jan
  • Holenstein, Thomas
  • Immorlica, Nicole
  • Izsak, Rani
  • Jain, Rahul
  • Jansen, Klaus
  • Jayram, T. S.
  • Jerrum, Mark
  • Jiang, Minghui
  • Jorati, Amin
  • Jozeph, Shlomo
  • Kanade, Varun
  • Karp, Jeremy A.
  • Katzman, Jonathan
  • Kleinberg, Robert
  • Klimm, Max
  • Klivans, Adam
  • Kolliopoulos, Stavros G.
  • Kondapally, Ranganath
  • Kortsarz, Guy
  • Kothari, Pravesh
  • Krivelevich, Michael
  • Kumar, Ravi
  • Kwok, Tsz Chiu
  • Könemann, Jochen
  • Lattanzi, Silvio
  • Lau, Lap Chi
  • Lee, Troy
  • Levi, Reut
  • Li, Shanfei
  • Liu, Jingcheng
  • Louis, Anand
  • Lu, Pinyan
  • Lucier, Brendan
  • Magniez, Frédéric
  • Makarychev, Yury
  • Mehrabian, Abbas
  • Meka, Raghu
  • Mittal, Shashi
  • Moore, Cristopher
  • Mossel, Elchanan
  • Moysoglou, Yannis
  • Natarajan, Abhiram
  • Nikzad, Afshin
  • Nutov, Zeev
  • Olver, Neil
  • Panigrahi, Debmalya
  • Perkins, Will
  • Piguet, Diana
  • Pokutta, Sebastian
  • Raghavendra, Prasad
  • Ravi, R.
  • Raz, Ran
  • Raßmann, Felicia
  • Reichman, Daniel
  • Reingold, Omer
  • Richerby, David
  • Rolim, José
  • Ron, Dana
  • Rubinfeld, Ronitt
  • Saks, Michael E.
  • Salavatipour, Mohammad R.
  • Samotij, Wojciech
  • Sanità, Laura
  • Schramm, Tselil
  • Schulz, Andreas S.
  • Schwartz, Roy
  • Seidell, Charles
  • Serna, Maria
  • Shraibman, Adi
  • Singh, Mohit
  • Skopalik, Alexander
  • Soper, Alan J.
  • Stefankovic, Daniel
  • Steinke, Thomas
  • Stiller, Sebastian
  • Strusevich, Vitaly A.
  • Stubbs, Daniel M.
  • Sudan, Madhu
  • Swamy, Chaitanya
  • Talwar, Kunal
  • Tamaki, Suguru
  • Taraz, Anusch
  • Tóth, Csaba D.
  • Umboh, Seeun
  • Vadhan, Salil
  • Venkat, Rakesh
  • Vigoda, Eric
  • Vilenchik, Dan
  • Vondrák, Jan
  • Vorsanger, Gregory
  • Wan, Andrew
  • Wang, Carol
  • Watson, Thomas
  • Weinberg, S. Matthew
  • Wenner, Cenny
  • Woodruff, David P.
  • Wormald, Nick
  • Wu, Yi
  • Yang, Linji
  • Yaroslavtsev, Grigory
  • Yoshida, Yuichi
  • Zhang, Chihao
  • Zhou, Yuan
    		•

    		  
    Frontmatter, Table of Contents, Preface, Conference Organization
    Authors: Jansen, Klaus ; Rolim, José ; Devanur, Nikhil R. ; Moore, Cristopher

    Abstract | Document (357 KB) | BibTeX

    Fully Dynamic All-Pairs Shortest Paths: Breaking the O(n) Barrier
    Authors: Abraham, Ittai ; Chechik, Shiri ; Talwar, Kunal

    Abstract | Document (484 KB) | BibTeX

    Approximation Algorithms for Minimum-Load k-Facility Location
    Authors: Ahmadian, Sara ; Behsaz, Babak ; Friggstad, Zachary ; Jorati, Amin ; Salavatipour, Mohammad R. ; Swamy, Chaitanya

    Abstract | Document (640 KB) | BibTeX

    The Cover Number of a Matrix and its Algorithmic Applications
    Authors: Alon, Noga ; Lee, Troy ; Shraibman, Adi

    Abstract | Document (464 KB) | BibTeX

    Network Design with Coverage Costs
    Authors: Barman, Siddharth ; Chawla, Shuchi ; Umboh, Seeun

    Abstract | Document (521 KB) | BibTeX

    Online Set Cover with Set Requests
    Authors: Bhawalkar, Kshipra ; Gollapudi, Sreenivas ; Panigrahi, Debmalya

    Abstract | Document (528 KB) | BibTeX

    Lowest Degree k-Spanner: Approximation and Hardness
    Authors: Chlamtác, Eden ; Dinitz, Michael

    Abstract | Document (527 KB) | BibTeX

    Improved Streaming Algorithms for Weighted Matching, via Unweighted Matching
    Authors: Crouch, Michael ; Stubbs, Daniel M.

    Abstract | Document (404 KB) | BibTeX

    Guruswami-Sinop Rounding without Higher Level Lasserre
    Authors: Deshpande, Amit ; Venkat, Rakesh

    Abstract | Document (473 KB) | BibTeX

    Improved Approximation Algorithm for Steiner k-Forest with Nearly Uniform Weights
    Authors: Dinitz, Michael ; Kortsarz, Guy ; Nutov, Zeev

    Abstract | Document (497 KB) | BibTeX

    Computing Opaque Interior Barriers à la Shermer
    Authors: Dumitrescu, Adrian ; Jiang, Minghui ; Tóth, Csaba D.

    Abstract | Document (627 KB) | BibTeX

    Hardness of Submodular Cost Allocation: Lattice Matching and a Simplex Coloring Conjecture
    Authors: Ene, Alina ; Vondrák, Jan

    Abstract | Document (534 KB) | BibTeX

    Constrained Monotone Function Maximization and the Supermodular Degree
    Authors: Feldman, Moran ; Izsak, Rani

    Abstract | Document (612 KB) | BibTeX

    On the Equivalence of the Bidirected and Hypergraphic Relaxations for Steiner Tree
    Authors: Feldmann, Andreas Emil ; Könemann, Jochen ; Olver, Neil ; Sanità, Laura

    Abstract | Document (532 KB) | BibTeX

    Reaching Consensus via Non-Bayesian Asynchronous Learning in Social Networks
    Authors: Feldman, Michal ; Immorlica, Nicole ; Lucier, Brendan ; Weinberg, S. Matthew

    Abstract | Document (483 KB) | BibTeX

    Deliver or hold: Approximation Algorithms for the Periodic Inventory Routing Problem
    Authors: Fukunaga, Takuro ; Nikzad, Afshin ; Ravi, R.

    Abstract | Document (455 KB) | BibTeX

    Complexity and Approximation of the Continuous Network Design Problem
    Authors: Gairing, Martin ; Harks, Tobias ; Klimm, Max

    Abstract | Document (564 KB) | BibTeX

    Approximate Pure Nash Equilibria in Weighted Congestion Games
    Authors: Hansknecht, Christoph ; Klimm, Max ; Skopalik, Alexander

    Abstract | Document (501 KB) | BibTeX

    Discrepancy Without Partial Colorings
    Authors: Harvey, Nicholas J. A. ; Schwartz, Roy ; Singh, Mohit

    Abstract | Document (500 KB) | BibTeX

    Universal Factor Graphs for Every NP-Hard Boolean CSP
    Authors: Jozeph, Shlomo

    Abstract | Document (371 KB) | BibTeX

    A 9/7 -Approximation Algorithm for Graphic TSP in Cubic Bipartite Graphs
    Authors: Karp, Jeremy A. ; Ravi, R.

    Abstract | Document (529 KB) | BibTeX

    Sherali-Adams Gaps, Flow-cover Inequalities and Generalized Configurations for Capacity-constrained Facility Location
    Authors: Kolliopoulos, Stavros G. ; Moysoglou, Yannis

    Abstract | Document (532 KB) | BibTeX

    Lower Bounds on Expansions of Graph Powers
    Authors: Kwok, Tsz Chiu ; Lau, Lap Chi

    Abstract | Document (459 KB) | BibTeX

    An Improved Approximation Algorithm for the Hard Uniform Capacitated k-median Problem
    Authors: Li, Shanfei

    Abstract | Document (578 KB) | BibTeX

    Approximation Algorithms for Hypergraph Small Set Expansion and Small Set Vertex Expansion
    Authors: Louis, Anand ; Makarychev, Yury

    Abstract | Document (547 KB) | BibTeX

    Robust Appointment Scheduling
    Authors: Mittal, Shashi ; Schulz, Andreas S. ; Stiller, Sebastian

    Abstract | Document (469 KB) | BibTeX

    Computational Complexity of Certifying Restricted Isometry Property
    Authors: Natarajan, Abhiram ; Wu, Yi

    Abstract | Document (430 KB) | BibTeX

    Gap Amplification for Small-Set Expansion via Random Walks
    Authors: Raghavendra, Prasad ; Schramm, Tselil

    Abstract | Document (412 KB) | BibTeX

    Power of Preemption on Uniform Parallel Machines
    Authors: Soper, Alan J. ; Strusevich, Vitaly A.

    Abstract | Document (347 KB) | BibTeX

    Improved Approximation Algorithms for Matroid and Knapsack Median Problems and Applications
    Authors: Swamy, Chaitanya

    Abstract | Document (580 KB) | BibTeX

    Robust Approximation of Temporal CSP
    Authors: Tamaki, Suguru ; Yoshida, Yuichi

    Abstract | Document (529 KB) | BibTeX

    Parity is Positively Useless
    Authors: Wenner, Cenny

    Abstract | Document (614 KB) | BibTeX

    The Condensation Phase Transition in Random Graph Coloring
    Authors: Bapst, Victor ; Coja-Oghlan, Amin ; Hetterich, Samuel ; Raßmann, Felicia ; Vilenchik, Dan

    Abstract | Document (582 KB) | BibTeX

    The Information Complexity of Hamming Distance
    Authors: Blais, Eric ; Brody, Joshua ; Ghazi, Badih

    Abstract | Document (633 KB) | BibTeX

    An Approximate Version of the Tree Packing Conjecture via Random Embeddings
    Authors: Böttcher, Julia ; Hladký, Jan ; Piguet, Diana ; Taraz, Anusch

    Abstract | Document (476 KB) | BibTeX

    On Sharp Thresholds in Random Geometric Graphs
    Authors: Bradonjic, Milan ; Perkins, Will

    Abstract | Document (488 KB) | BibTeX

    Average Case Polyhedral Complexity of the Maximum Stable Set Problem
    Authors: Braun, Gábor ; Fiorini, Samuel ; Pokutta, Sebastian

    Abstract | Document (560 KB) | BibTeX

    An Optimal Algorithm for Large Frequency Moments Using O(n^(1-2/k)) Bits
    Authors: Braverman, Vladimir ; Katzman, Jonathan ; Seidell, Charles ; Vorsanger, Gregory

    Abstract | Document (517 KB) | BibTeX

    Certifying Equality With Limited Interaction
    Authors: Brody, Joshua ; Chakrabarti, Amit ; Kondapally, Ranganath ; Woodruff, David P. ; Yaroslavtsev, Grigory

    Abstract | Document (738 KB) | BibTeX

    #BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Non-uniqueness Region
    Authors: Cai, Jin-Yi ; Galanis, Andreas ; Goldberg, Leslie Ann ; Guo, Heng ; Jerrum, Mark ; Stefankovic, Daniel ; Vigoda, Eric

    Abstract | Document (537 KB) | BibTeX

    The Power of Super-logarithmic Number of Players
    Authors: Chattopadhyay, Arkadev ; Saks, Michael E.

    Abstract | Document (433 KB) | BibTeX

    On Reconstructing a Hidden Permutation
    Authors: Chierichetti, Flavio ; Dasgupta, Anirban ; Kumar, Ravi ; Lattanzi, Silvio

    Abstract | Document (429 KB) | BibTeX

    Two Sides of the Coin Problem
    Authors: Cohen, Gil ; Ganor, Anat ; Raz, Ran

    Abstract | Document (495 KB) | BibTeX

    Absorption Time of the Moran Process
    Authors: Díaz, Josep ; Goldberg, Leslie Ann ; Richerby, David ; Serna, Maria

    Abstract | Document (463 KB) | BibTeX

    Sampling a Uniform Solution of a Quadratic Equation Modulo a Prime Power
    Authors: Dubey, Chandan ; Holenstein, Thomas

    Abstract | Document (497 KB) | BibTeX

    Unidirectional Input/Output Streaming Complexity of Reversal and Sorting
    Authors: François, Nathanaël ; Jain, Rahul ; Magniez, Frédéric

    Abstract | Document (536 KB) | BibTeX

    Improved Lower Bounds for Testing Triangle-freeness in Boolean Functions via Fast Matrix Multiplication
    Authors: Fu, Hu ; Kleinberg, Robert

    Abstract | Document (457 KB) | BibTeX

    Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
    Authors: Galanis, Andreas ; Stefankovic, Daniel ; Vigoda, Eric ; Yang, Linji

    Abstract | Document (540 KB) | BibTeX

    Space Pseudorandom Generators by Communication Complexity Lower Bounds
    Authors: Ganor, Anat ; Raz, Ran

    Abstract | Document (492 KB) | BibTeX

    On Multiple Input Problems in Property Testing
    Authors: Goldreich, Oded

    Abstract | Document (541 KB) | BibTeX

    Communication Complexity of Set-Disjointness for All Probabilities
    Authors: Göös, Mika ; Watson, Thomas

    Abstract | Document (733 KB) | BibTeX

    List Decoding Group Homomorphisms Between Supersolvable Groups
    Authors: Guo, Alan ; Sudan, Madhu

    Abstract | Document (552 KB) | BibTeX

    Evading Subspaces Over Large Fields and Explicit List-decodable Rank-metric Codes
    Authors: Guruswami, Venkatesan ; Wang, Carol

    Abstract | Document (453 KB) | BibTeX

    Exchangeability and Realizability: De Finetti Theorems on Graphs
    Authors: Jayram, T. S. ; Vondrák, Jan

    Abstract | Document (492 KB) | BibTeX

    Global and Local Information in Clustering Labeled Block Models
    Authors: Kanade, Varun ; Mossel, Elchanan ; Schramm, Tselil

    Abstract | Document (611 KB) | BibTeX

    Embedding Hard Learning Problems Into Gaussian Space
    Authors: Klivans, Adam ; Kothari, Pravesh

    Abstract | Document (483 KB) | BibTeX

    Smoothed Analysis on Connected Graphs
    Authors: Krivelevich, Michael ; Reichman, Daniel ; Samotij, Wojciech

    Abstract | Document (491 KB) | BibTeX

    Local Algorithms for Sparse Spanning Graphs
    Authors: Levi, Reut ; Ron, Dana ; Rubinfeld, Ronitt

    Abstract | Document (509 KB) | BibTeX

    The Complexity of Ferromagnetic Two-spin Systems with External Fields
    Authors: Liu, Jingcheng ; Lu, Pinyan ; Zhang, Chihao

    Abstract | Document (577 KB) | BibTeX

    It’s a Small World for Random Surfers
    Authors: Mehrabian, Abbas ; Wormald, Nick

    Abstract | Document (518 KB) | BibTeX

    Deterministic Coupon Collection and Better Strong Dispersers
    Authors: Meka, Raghu ; Reingold, Omer ; Zhou, Yuan

    Abstract | Document (502 KB) | BibTeX

    Pseudorandomness and Fourier Growth Bounds for Width-3 Branching Programs
    Authors: Steinke, Thomas ; Vadhan, Salil ; Wan, Andrew

    Abstract | Document (560 KB) | BibTeX

    		  



    DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI