Approximation, randomization, and combinatorial optimization : algorithms and techniques : 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012. Proceedings / Anupam Gupta [and others] (eds.).

By: (15th : International Workshop on Randomization and Approximation Techniques in Computer Science (15th : 2012 : Cambridge, Mass.)
Contributor(s): Gupta, Anupam
Material type: TextTextSeries: SerienbezeichnungLecture notes in computer science: 7408.; LNCS sublibrary: Publisher: Berlin ; Heidelberg : Springer Science+Business Media, ©2012Description: 1 online resource (xv, 674 pages) : illustrationsContent type: text Media type: computer Carrier type: online resourceISBN: 9783642325120; 3642325122Other title: APPROX 2012 | RANDOM 2012Subject(s): Mathematical optimization -- Congresses | Computational complexity -- Congresses | Informatique | Computational complexity | Mathematical optimization | Electronic data processing | Computer vision | Probability and Statistics in Computer Science | Computer Imaging, Vision, Pattern Recognition and Graphics | computerwetenschappen | computer sciences | numerieke methoden | numerical methods | computertechnieken | computer techniques | waarschijnlijkheid | probability | statistiek | statistics | wiskunde | mathematics | patroonherkenning | pattern recognition | machine vision | algoritmen | algorithms | computeranalyse | computer analysis | computational science | Information and Communication Technology (General) | Informatie- en communicatietechnologie (algemeen)Genre/Form: Electronic books. | Electronic books. | Conference papers and proceedings. DDC classification: 519.64 LOC classification: QA402.5 | .I58 2012Online resources: Click here to access online
Contents:
A New Point of NP-Hardness for 2-to-1 Label Cover / Per Austrin, Ryan O'Donnell and John Wright -- Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems / Per Austrin, Toniann Pitassi and Yu Wu -- Additive Approximation for Near-Perfect Phylogeny Construction / Pranjal Awasthi, Avrim Blum, Jamie Morgenstern and Or Sheffet -- Improved Spectral-Norm Bounds for Clustering / Pranjal Awasthi and Or Sheffet -- Primal-Dual Approximation Algorithms for Node-Weighted Network Design in Planar Graphs / Piotr Berman and Grigory Yaroslavtsev -- What's the Frequency, Kenneth?: Sublinear Fourier Sampling Off the Grid / Petros Boufounos, Volkan Cevher, Anna C. Gilbert, Yi Li and Martin J. Strauss -- Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply / Parinya Chalermsook, Julia Chuzhoy, Sampath Kannan and Sanjeev Khanna -- Online Flow Time Scheduling in the Presence of Preemption Overhead / Ho-Leung Chan, Tak-Wah Lam and Rongbin Li -- Prize-Collecting Survivable Network Design in Node-Weighted Graphs / Chandra Chekuri, Alina Ene and Ali Vakilian -- Approximating Minimum-Cost Connected T-Joins / Joseph Cheriyan, Zachary Friggstad and Zhihan Gao -- iBGP and Constrained Connectivity / Michael Dinitz and Gordon Wilfong -- Online Scheduling of Jobs with Fixed Start Times on Related Machines / Leah Epstein, Łukasz Jeż, Jiří Sgall and Rob van Stee -- A Systematic Approach to Bound Factor Revealing LPs and Its Application to the Metric and Squared Metric Facility Location Problems / Cristina G. Fernandes, Luís A.A. Meira, Flávio K. Miyazawa and Lehilton L.C. Pedrosa -- Approximating Bounded Occurrence Ordering CSPs / Venkatesan Guruswami and Yuan Zhou -- On the NP-Hardness of Max-Not-2 / Johan Håstad -- The Remote Set Problem on Lattices / Ishay Haviv -- Approximation Algorithms for Generalized and Variable-Sized Bin Covering / Matthias Hellwig and Alexander Souza -- Approximating Minimum Linear Ordering Problems / Satoru Iwata, Prasad Tetali and Pushkar Tripathi -- New Approximation Results for Resource Replication Problems / Samir Khuller, Barna Saha and Kanthi K. Sarpatwar -- Maximum Matching in Semi-streaming with Few Passes / Christian Konrad, Frédéric Magniez and Claire Mathieu -- Improved Inapproximability for TSP / Michael Lampis -- Approximation Algorithm for Non-boolean MAX k-CSP / Konstantin Makarychev and Yury Makarychev -- Planarizing an Unknown Surface / Yury Makarychev and Anastasios Sidiropoulos -- The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover / Dana Moshkovitz -- New and Improved Bounds for the Minimum Set Cover Problem / Rishi Saket and Maxim Sviridenko -- Hardness of Vertex Deletion and Project Scheduling / Ola Svensson -- Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues / Suguru Tamaki and Yuichi Yoshida -- Circumventing d-to-1 for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width Four Cenny Wenner -- Spectral Norm of Symmetric Functions / Anil Ada, Omar Fawzi and Hamed Hatami -- Almost K-Wise vs. K-Wise Independent Permutations, and Uniformity for General Group Actions / Noga Alon and Shachar Lovett -- Testing Permanent Oracles -- Revisited / Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran and Sushant Sachdeva -- Limitations of Local Filters of Lipschitz and Monotone Functions / Pranjal Awasthi, Madhav Jha, Marco Molinaro and Sofya Raskhodnikova -- Testing Lipschitz Functions on Hypergrid Domains / Pranjal Awasthi, Madhav Jha, Marco Molinaro and Sofya Raskhodnikova -- Extractors for Polynomials Sources over Constant-Size Fields of Small Characteristic / Eli Ben-Sasson and Ariel Gabizon -- Multiple-Choice Balanced Allocation in (Almost) Parallel / Petra Berenbrink, Artur Czumaj, Matthias Englert, Tom Friedetzky and Lars Nagel -- Optimal Hitting Sets for Combinatorial Shapes / Aditya Bhaskara, Devendra Desai and Srikanth Srinivasan -- Tight Bounds for Testing k-Linearity / Eric Blais and Daniel Kane -- Pseudorandomness for Linear Length Branching Programs and Stack Machines / Andrej Bogdanov, Periklis A. Papakonstantinou and Andrew Wan -- A Discrepancy Lower Bound for Information Complexity / Mark Braverman and Omri Weinstein -- On the Coin Weighing Problem with the Presence of Noise / Nader H. Bshouty -- Information Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming / Amit Chakrabarti, Ranganath Kondapally and Zhenghui Wang -- An Explicit VC-Theorem for Low-Degree Polynomials / Eshan Chattopadhyay, Adam Klivans and Pravesh Kothari -- Tight Bounds on the Threshold for Permuted k-Colorability / Varsha Dani, Cristopher Moore and Anna Olson -- Sparse and Lopsided Set Disjointness via Information Theory / Anirban Dasgupta, Ravi Kumar and D. Sivakumar -- Maximal Empty Boxes Amidst Random Points / Adrian Dumitrescu and Minghui Jiang -- Rainbow Connectivity of Sparse Random Graphs / Alan Frieze and Charalampos E. Tsourakakis -- Invertible Zero-Error Dispersers and Defective Memory with Stuck-At Errors / Ariel Gabizon and Ronen Shaltiel -- Two-Sided Error Proximity Oblivious Testing Oded Goldreich and Igor Shinkar -- Mirror Descent Based Database Privacy / Prateek Jain and Abhradeep Thakurta -- Analysis of k-Means++ for Separable Data / Ragesh Jaiswal and Nitin Garg -- A Sharper Local Lemma with Improved Applications / Kashyap Kolipaka, Mario Szegedy and Yixin Xu -- Finding Small Sparse Cuts by Random Walk / Tsz Chiu Kwok and Lap Chi Lau -- On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation / Jelani Nelson, Huy L. Nguyễn and David P. Woodruff -- A New Upper Bound on the Query Complexity for Testing Generalized Reed-Muller codes / Noga Ron-Zewi and Madhu Sudan -- A Combination of Testability and Decodability by Tensor Products / Michael Viderman -- Extractors for Turing-Machine Sources / Emanuele Viola.
Summary: Annotation This book constitutes the joint refereed proceedings of the 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2012, and the 16th International Workshop on Randomization and Computation, RANDOM 2012, held in Cambridge, Massachusetts, USA, in August 2011. The volume contains 28 contributed papers, selected by the APPROX Program Committee out of 70 submissions, and 28 contributed papers, selected by the RANDOM Program Committee out of 67 submissions. APPROX focuses on algorithmic and complexity issues surrounding the development of efficient approximate solutions to computationally difficult problems. RANDOM is concerned with applications of randomness to computational and combinatorial problems.
Tags from this library: No tags from this library for this title. Log in to add tags.
    Average rating: 0.0 (0 votes)
Item type Current location Collection Call number Status Date due Barcode Item holds
eBook eBook e-Library

Electronic Book@IST

EBook Available
Total holds: 0

A New Point of NP-Hardness for 2-to-1 Label Cover / Per Austrin, Ryan O'Donnell and John Wright -- Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems / Per Austrin, Toniann Pitassi and Yu Wu -- Additive Approximation for Near-Perfect Phylogeny Construction / Pranjal Awasthi, Avrim Blum, Jamie Morgenstern and Or Sheffet -- Improved Spectral-Norm Bounds for Clustering / Pranjal Awasthi and Or Sheffet -- Primal-Dual Approximation Algorithms for Node-Weighted Network Design in Planar Graphs / Piotr Berman and Grigory Yaroslavtsev -- What's the Frequency, Kenneth?: Sublinear Fourier Sampling Off the Grid / Petros Boufounos, Volkan Cevher, Anna C. Gilbert, Yi Li and Martin J. Strauss -- Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply / Parinya Chalermsook, Julia Chuzhoy, Sampath Kannan and Sanjeev Khanna -- Online Flow Time Scheduling in the Presence of Preemption Overhead / Ho-Leung Chan, Tak-Wah Lam and Rongbin Li -- Prize-Collecting Survivable Network Design in Node-Weighted Graphs / Chandra Chekuri, Alina Ene and Ali Vakilian -- Approximating Minimum-Cost Connected T-Joins / Joseph Cheriyan, Zachary Friggstad and Zhihan Gao -- iBGP and Constrained Connectivity / Michael Dinitz and Gordon Wilfong -- Online Scheduling of Jobs with Fixed Start Times on Related Machines / Leah Epstein, Łukasz Jeż, Jiří Sgall and Rob van Stee -- A Systematic Approach to Bound Factor Revealing LPs and Its Application to the Metric and Squared Metric Facility Location Problems / Cristina G. Fernandes, Luís A.A. Meira, Flávio K. Miyazawa and Lehilton L.C. Pedrosa -- Approximating Bounded Occurrence Ordering CSPs / Venkatesan Guruswami and Yuan Zhou -- On the NP-Hardness of Max-Not-2 / Johan Håstad -- The Remote Set Problem on Lattices / Ishay Haviv -- Approximation Algorithms for Generalized and Variable-Sized Bin Covering / Matthias Hellwig and Alexander Souza -- Approximating Minimum Linear Ordering Problems / Satoru Iwata, Prasad Tetali and Pushkar Tripathi -- New Approximation Results for Resource Replication Problems / Samir Khuller, Barna Saha and Kanthi K. Sarpatwar -- Maximum Matching in Semi-streaming with Few Passes / Christian Konrad, Frédéric Magniez and Claire Mathieu -- Improved Inapproximability for TSP / Michael Lampis -- Approximation Algorithm for Non-boolean MAX k-CSP / Konstantin Makarychev and Yury Makarychev -- Planarizing an Unknown Surface / Yury Makarychev and Anastasios Sidiropoulos -- The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover / Dana Moshkovitz -- New and Improved Bounds for the Minimum Set Cover Problem / Rishi Saket and Maxim Sviridenko -- Hardness of Vertex Deletion and Project Scheduling / Ola Svensson -- Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues / Suguru Tamaki and Yuichi Yoshida -- Circumventing d-to-1 for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width Four (Extended Abstract) / Cenny Wenner -- Spectral Norm of Symmetric Functions / Anil Ada, Omar Fawzi and Hamed Hatami -- Almost K-Wise vs. K-Wise Independent Permutations, and Uniformity for General Group Actions / Noga Alon and Shachar Lovett -- Testing Permanent Oracles -- Revisited / Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran and Sushant Sachdeva -- Limitations of Local Filters of Lipschitz and Monotone Functions / Pranjal Awasthi, Madhav Jha, Marco Molinaro and Sofya Raskhodnikova -- Testing Lipschitz Functions on Hypergrid Domains / Pranjal Awasthi, Madhav Jha, Marco Molinaro and Sofya Raskhodnikova -- Extractors for Polynomials Sources over Constant-Size Fields of Small Characteristic / Eli Ben-Sasson and Ariel Gabizon -- Multiple-Choice Balanced Allocation in (Almost) Parallel / Petra Berenbrink, Artur Czumaj, Matthias Englert, Tom Friedetzky and Lars Nagel -- Optimal Hitting Sets for Combinatorial Shapes / Aditya Bhaskara, Devendra Desai and Srikanth Srinivasan -- Tight Bounds for Testing k-Linearity / Eric Blais and Daniel Kane -- Pseudorandomness for Linear Length Branching Programs and Stack Machines / Andrej Bogdanov, Periklis A. Papakonstantinou and Andrew Wan -- A Discrepancy Lower Bound for Information Complexity / Mark Braverman and Omri Weinstein -- On the Coin Weighing Problem with the Presence of Noise / Nader H. Bshouty -- Information Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming / Amit Chakrabarti, Ranganath Kondapally and Zhenghui Wang -- An Explicit VC-Theorem for Low-Degree Polynomials / Eshan Chattopadhyay, Adam Klivans and Pravesh Kothari -- Tight Bounds on the Threshold for Permuted k-Colorability / Varsha Dani, Cristopher Moore and Anna Olson -- Sparse and Lopsided Set Disjointness via Information Theory / Anirban Dasgupta, Ravi Kumar and D. Sivakumar -- Maximal Empty Boxes Amidst Random Points / Adrian Dumitrescu and Minghui Jiang -- Rainbow Connectivity of Sparse Random Graphs / Alan Frieze and Charalampos E. Tsourakakis -- Invertible Zero-Error Dispersers and Defective Memory with Stuck-At Errors / Ariel Gabizon and Ronen Shaltiel -- Two-Sided Error Proximity Oblivious Testing (Extended Abstract) / Oded Goldreich and Igor Shinkar -- Mirror Descent Based Database Privacy / Prateek Jain and Abhradeep Thakurta -- Analysis of k-Means++ for Separable Data / Ragesh Jaiswal and Nitin Garg -- A Sharper Local Lemma with Improved Applications / Kashyap Kolipaka, Mario Szegedy and Yixin Xu -- Finding Small Sparse Cuts by Random Walk / Tsz Chiu Kwok and Lap Chi Lau -- On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation / Jelani Nelson, Huy L. Nguyễn and David P. Woodruff -- A New Upper Bound on the Query Complexity for Testing Generalized Reed-Muller codes / Noga Ron-Zewi and Madhu Sudan -- A Combination of Testability and Decodability by Tensor Products / Michael Viderman -- Extractors for Turing-Machine Sources / Emanuele Viola.

Includes bibliographical references and index.

Online resource; title from PDF title page (SpringerLink, viewed Aug. 23, 2012).

Annotation This book constitutes the joint refereed proceedings of the 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2012, and the 16th International Workshop on Randomization and Computation, RANDOM 2012, held in Cambridge, Massachusetts, USA, in August 2011. The volume contains 28 contributed papers, selected by the APPROX Program Committee out of 70 submissions, and 28 contributed papers, selected by the RANDOM Program Committee out of 67 submissions. APPROX focuses on algorithmic and complexity issues surrounding the development of efficient approximate solutions to computationally difficult problems. RANDOM is concerned with applications of randomness to computational and combinatorial problems.

There are no comments for this item.

to post a comment.

Powered by Koha