Title Approximation, randomization, and combinatorial optimization : algorithms and techniques : 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013 ; proceedings / Prasad Raghavendra [and others] (eds.)

Published Heidelberg : Springer, [2013]

Click on the following:
Springer Computer Science eBooks
Springer eBooks

Copies

Description 1 online resource (xiv, 716 pages) : illustrations Series Lecture notes in computer science, 0302-9743 ; 8096 LNCS sublibrary. SL 1, Theoretical computer science and general issues Lecture notes in computer science ; 8096. LNCS sublibrary. SL 1, Theoretical computer science and general issues. Contents APPROX. Spectral Sparsification in Dynamic Graph Streams / Kook Jin Ahn, Sudipto Guha, Andrew McGregor -- The Online Stochastic Generalized Assignment Problem / Saeed Alaei, MohammadTaghi Hajiaghayi, Vahid Liaghat -- On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems / Per Austrin, Rajsekar Manokaran, Cenny Wenner -- Approximating Large Frequency Moments with Pick-and-Drop Sampling / Vladimir Braverman, Rafail Ostrovsky -- Generalizing the Layering Method of Indyk and Woodruff: Recursive Sketches for Frequency-Based Vectors on Streams / Vladimir Braverman, Rafail Ostrovsky -- Capacitated Network Design on Undirected Graphs / Deeparnab Chakrabarty ... et al. -- Scheduling Subset Tests: One-Time, Continuous, and How They Relate / Edith Cohen, Haim Kaplan, Yishay Mansour -- On the Total Perimeter of Homothetic Convex Bodies in a Convex Container / Adrian Dumitrescu, Csaba D. Tóth Partial Interval Set Cover -- Trade-Offs between Scalability and Optimality / Katherine Edwards, Simon Griffiths, William Sean Kennedy -- Online Square-into-Square Packing / Sándor P. Fekete, Hella-Franziska Hoffmann -- Online Non-clairvoyant Scheduling to Simultaneously Minimize All Convex Functions / Kyle Fox ... et al. -- Shrinking Maxima, Decreasing Costs: New Online Packing and Covering Problems / Pierre Fraigniaud ... et al. -- Multiple Traveling Salesmen in Asymmetric Metrics / Zachary Friggstad -- Approximate Indexability and Bandit Problems with Concave Rewards and Delayed Feedback / Sudipto Guha, Kamesh Munagala -- The Approximability of the Binary Paintshop Problem / Anupam Gupta ... et al. -- Approximation Algorithms for Movement Repairmen / MohammadTaghi Hajiaghayi ... et al. -- Improved Hardness of Approximating Chromatic Number / Sangxia Huang A Pseudo-approximation for the Genus of Hamiltonian Graphs / Yury Makarychev, Amir Nayyeri, Anastasios Sidiropoulos -- A Local Computation Approximation Scheme to Maximum Matching / Yishay Mansour, Shai Vardi -- Sketching Earth-Mover Distance on Graph Metrics / Andrew McGregor, Daniel Stubbs -- Online Multidimensional Load Balancing / Adam Meyerson, Alan Roytman, Brian Tagiku -- A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs / Shayan Oveis Gharan, Luca Trevisan -- Interdiction Problems on Planar Graphs / Feng Pan, Aaron Schild -- RANDOM. Conditional Random Fields, Planted Constraint Satisfaction and Entropy Concentration / Emmanuel Abbe, Andrea Montanari -- Finding Heavy Hitters from Lossy or Noisy Data / Lucia Batman ... et al. -- Private Learning and Sanitization: Pure vs. Approximate Differential Privacy / Amos Beimel, Kobbi Nissim, Uri Stemmer Phase Coexistence and Slow Mixing for the Hard-Core Model on Z2 / Antonio Blanca ... et al. -- Fast Private Data Release Algorithms for Sparse Queries / Avrim Blum, Aaron Roth -- Local Reconstructors and Tolerant Testers for Connectivity and Diameter / Andrea Campagna, Alan Guo, Ronitt Rubinfeld -- An Optimal Lower Bound for Monotonicity Testing over Hypergrids / Deeparnab Chakrabarty, C. Seshadhri -- Small-Bias Sets for Nonabelian Groups / Sixia Chen, Cristopher Moore, Alexander Russell -- What You Can Do with Coordinated Samples / Edith Cohen, Haim Kaplan -- Robust Randomness Amplifiers: Upper and Lower Bounds / Matthew Coudron, Thomas Vidick, Henry Yuen -- The Power of Choice for Random Satisfiability / Varsha Dani ... et al. -- Connectivity of Random High Dimensional Geometric Graphs / Roee David, Uriel Feige -- Matching-Vector Families and LDCs over Large Modulo / Zeev Dvir, Guangda Hu -- Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing / Michael A. Forbes, Amir Shpilka Testing Membership in Counter Automaton Languages / Yonatan Goldhirsh, Michael Viderman -- Tight Lower Bounds for Testing Linear Isomorphism / Elena Grigorescu, Karl Wimmer, Ning Xie -- Randomness-Efficient Curve Samplers / Zeyu Guo -- Combinatorial Limitations of Average-Radius List Decoding / Venkatesan Guruswami, Srivatsan Narayanan -- Zero Knowledge LTCs and Their Applications / Yuval Ishai ... et al. -- A Tight Lower Bound for High Frequency Moment Estimation with Small Error / Yi Li, David P. Woodruff -- Improved FPTAS for Multi-spin Systems / Pinyan Lu, Yitong Yin -- Pseudorandomness for Regular Branching Programs via Fourier Analysis / Omer Reingold, Thomas Steinke, Salil Vadhan -- Absolutely Sound Testing of Lifted Codes / Elad Haramaty, Noga Ron-Zewi, Madhu Sudan -- On the Average Sensitivity and Density of k-CNF Formulas / Dominik Scheder, Li-Yang Tan -- Improved Bounds on the Phase Transition for the Hard-Core Model in 2-Dimensions / Juan C. Vera, Eric Vigoda, Linji Yang Summary This book constitutes the proceedings of the 16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2013, and the 17th International Workshop on Randomization and Computation, RANDOM 2013, held in August 2013 in the USA. The total of 48 carefully reviewed and selected papers presented in this volume consist of 23 APPROX papers selected out of 46 submissions, and 25 RANDOM papers selected out of 52 submissions. APPROX 2013 focuses on algorithmic and complexity theoretic issues relevant to the development of efficient approximate solutions to computationally difficult problems, while RANDOM 2013 focuses on applications of randomness to computational and combinatorial problems Analysis computerwetenschappen computer sciences numerieke methoden numerical methods computertechnieken computer techniques waarschijnlijkheid probability statistiek statistics wiskunde mathematics algoritmen algorithms computeranalyse computer analysis gegevensstructuren data structures computational science Information and Communication Technology (General) Informatie- en communicatietechnologie (algemeen) Bibliography Includes bibliographical references and index Notes Print version record Subject Computer science -- Statistical methods -- Congresses Computer algorithms -- Congresses Approximation algorithms -- Congresses Statistics. Algorthms Statistics as Topic Algorithms algorithms. statistics. Statistics Approximation algorithms Computer algorithms Computer science -- Statistical methods Genre/Form proceedings (reports) Conference papers and proceedings Conference papers and proceedings. Actes de congrès. Form Electronic book Author Raghavendra, Prasad, editor International Workshop on Randomization and Computation (17th : 2013 : Berkeley, Calif.) ISBN 9783642403286 364240328X

Other Titles APPROX 2013 RANDOM 2013

  Permalink