Coverart for item
The Resource 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.)

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.)

Label
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
Title
Approximation, randomization, and combinatorial optimization
Title remainder
algorithms and techniques : 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012. Proceedings
Statement of responsibility
Anupam Gupta [and others] (eds.)
Title variation
  • APPROX 2012
  • RANDOM 2012
Creator
Contributor
Subject
Genre
Language
eng
Summary
Annotation
Member of
Cataloging source
GW5XE
Dewey number
519.64
Illustrations
illustrations
Index
index present
LC call number
QA402.5
LC item number
.I58 2012
Literary form
essays
http://bibfra.me/vocab/lite/meetingDate
2012
http://bibfra.me/vocab/lite/meetingName
International Workshop on Randomization and Approximation Techniques in Computer Science
Nature of contents
  • dictionaries
  • bibliography
http://library.link/vocab/relatedWorkOrContributorName
Gupta, Anupam
Series statement
  • Lecture notes in computer science,
  • LNCS sublibrary. SL 1, Theoretical computer science and general issues
Series volume
7408
http://library.link/vocab/subjectName
  • Mathematical optimization
  • Computational complexity
  • Informatique
  • Computational complexity
  • Mathematical optimization
Summary expansion
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
Label
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.)
Instantiates
Publication
Antecedent source
unknown
Bibliography note
Includes bibliographical references and index
Carrier category
online resource
Carrier category code
  • cr
Carrier MARC source
rdacarrier
Color
multicolored
Content category
text
Content type code
  • txt
Content type MARC source
rdacontent
Contents
  • Primal-Dual Approximation Algorithms for Node-Weighted Network Design in Planar Graphs
  • 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{circ}ẽn and David P. Woodruff
  • Piotr Berman and Grigory Yaroslavtsev
  • 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
  • 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
  • A New Point of NP-Hardness for 2-to-1 Label Cover
  • 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
  • Per Austrin, Ryan O'Donnell and John Wright
  • 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
  • Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems
  • 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
  • Per Austrin, Toniann Pitassi and Yu Wu
  • 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
  • Additive Approximation for Near-Perfect Phylogeny Construction
  • 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
  • Pranjal Awasthi, Avrim Blum, Jamie Morgenstern and Or Sheffet
  • 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
  • Improved Spectral-Norm Bounds for Clustering
  • 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
  • Pranjal Awasthi and Or Sheffet
  • 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
Control code
802338166
Dimensions
unknown
Extent
1 online resource (xv, 674 pages)
File format
unknown
Form of item
online
Isbn
9783642325120
Lccn
2012943609
Level of compression
unknown
Media category
computer
Media MARC source
rdamedia
Media type code
  • c
Other physical details
illustrations.
Quality assurance targets
not applicable
Reformatting quality
unknown
Sound
unknown sound
Specific material designation
remote
System control number
(OCoLC)802338166
Label
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.)
Publication
Antecedent source
unknown
Bibliography note
Includes bibliographical references and index
Carrier category
online resource
Carrier category code
  • cr
Carrier MARC source
rdacarrier
Color
multicolored
Content category
text
Content type code
  • txt
Content type MARC source
rdacontent
Contents
  • Primal-Dual Approximation Algorithms for Node-Weighted Network Design in Planar Graphs
  • 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{circ}ẽn and David P. Woodruff
  • Piotr Berman and Grigory Yaroslavtsev
  • 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
  • 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
  • A New Point of NP-Hardness for 2-to-1 Label Cover
  • 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
  • Per Austrin, Ryan O'Donnell and John Wright
  • 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
  • Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems
  • 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
  • Per Austrin, Toniann Pitassi and Yu Wu
  • 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
  • Additive Approximation for Near-Perfect Phylogeny Construction
  • 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
  • Pranjal Awasthi, Avrim Blum, Jamie Morgenstern and Or Sheffet
  • 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
  • Improved Spectral-Norm Bounds for Clustering
  • 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
  • Pranjal Awasthi and Or Sheffet
  • 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
Control code
802338166
Dimensions
unknown
Extent
1 online resource (xv, 674 pages)
File format
unknown
Form of item
online
Isbn
9783642325120
Lccn
2012943609
Level of compression
unknown
Media category
computer
Media MARC source
rdamedia
Media type code
  • c
Other physical details
illustrations.
Quality assurance targets
not applicable
Reformatting quality
unknown
Sound
unknown sound
Specific material designation
remote
System control number
(OCoLC)802338166

Library Locations

    • Ellis LibraryBorrow it
      1020 Lowry Street, Columbia, MO, 65201, US
      38.944491 -92.326012
    • Engineering Library & Technology CommonsBorrow it
      W2001 Lafferre Hall, Columbia, MO, 65211, US
      38.946102 -92.330125
Processing Feedback ...