2011 share record
persistent URL:
Mohammed Amin Abdullah , Colin Cooper , Moez Draief : Viral Processes by Random Walks on Random Regular Graphs. APPROX-RANDOM 2011 : 351-364 share record
persistent URL:
Andris Ambainis , Andrew M. Childs , Yi-Kai Liu : Quantum Property Testing for Bounded-Degree Graphs. APPROX-RANDOM 2011 : 365-376 share record
persistent URL:
Sanjeev Arora , Rong Ge : New Tools for Graph Coloring. APPROX-RANDOM 2011 : 1-12 share record
persistent URL:
Sergei Artemenko , Ronen Shaltiel : Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification. APPROX-RANDOM 2011 : 377-388 share record
persistent URL:
Per Austrin , Mark Braverman , Eden Chlamtac : Inapproximability of NP-Complete Variants of Nash Equilibrium. APPROX-RANDOM 2011 : 13-25 share record
persistent URL:
Lidor Avigad , Oded Goldreich : Testing Graph Blow-Up. APPROX-RANDOM 2011 : 389-399 share record
persistent URL:
Khanh Do Ba , Piotr Indyk : Sparse Recovery with Partial Support Knowledge. APPROX-RANDOM 2011 : 26-37 share record
persistent URL:
Nikhil Bansal , Ravishankar Krishnaswamy , Barna Saha : On Capacitated Set Cover Problems. APPROX-RANDOM 2011 : 38-49 share record
persistent URL:
Yair Bartal , Douglas E. Carroll , Adam Meyerson , Ofer Neiman : Bandwidth and Low Dimensional Embedding. APPROX-RANDOM 2011 : 50-61 export record
dblp key:
conf/approx/Ben-SassonGMSS11 share record
persistent URL:
Eli Ben-Sasson , Elena Grigorescu , Ghid Maatouk , Amir Shpilka , Madhu Sudan : On Sums of Locally Testable Affine Invariant Properties. APPROX-RANDOM 2011 : 400-411 export record
dblp key:
conf/approx/Ben-SassonS11 share record
persistent URL:
Eli Ben-Sasson , Madhu Sudan : Limits on the Rate of Locally Testable Affine-Invariant Codes. APPROX-RANDOM 2011 : 412-423 share record
persistent URL:
Piotr Berman , Erik D. Demaine , Morteza Zadimoghaddam : O(1)-Approximations for Maximum Movement Problems. APPROX-RANDOM 2011 : 62-74 share record
persistent URL:
Anand Bhalgat , Deeparnab Chakrabarty , Sanjeev Khanna : Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs. APPROX-RANDOM 2011 : 75-86 share record
persistent URL:
Anand Bhalgat , Deeparnab Chakrabarty , Sanjeev Khanna : Social Welfare in One-Sided Matching Markets without Money. APPROX-RANDOM 2011 : 87-98 export record
dblp key:
conf/approx/BhatnagarBM11 share record
persistent URL:
Nayantara Bhatnagar , Andrej Bogdanov , Elchanan Mossel : The Computational Complexity of Estimating MCMC Convergence Time. APPROX-RANDOM 2011 : 424-435 share record
persistent URL:
Joshua Brody , David P. Woodruff : Streaming Algorithms with One-Sided Estimation. APPROX-RANDOM 2011 : 436-447 share record
persistent URL:
Tim Carnes , David B. Shmoys : Primal-Dual Schema and Lagrangian Relaxation for the k-Location-Routing Problem. APPROX-RANDOM 2011 : 99-110 export record
dblp key:
conf/approx/ChakaravarthyKPRS11 share record
persistent URL:
Venkatesan T. Chakaravarthy , Amit Kumar , Vinayaka Pandit , Sambuddha Roy , Yogish Sabharwal : Scheduling Resources for Throughput Maximization. APPROX-RANDOM 2011 : 111-122 export record
dblp key:
conf/approx/ChakrabartiK11 share record
persistent URL:
Amit Chakrabarti , Ranganath Kondapally : Everywhere-Tight Information Cost Tradeoffs for Augmented Index. APPROX-RANDOM 2011 : 448-459 export record
dblp key:
conf/approx/Chalermsook11 share record
persistent URL:
Parinya Chalermsook : Coloring and Maximum Independent Set of Rectangles. APPROX-RANDOM 2011 : 123-134 share record
persistent URL:
Maurice Cheung , David B. Shmoys : A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems. APPROX-RANDOM 2011 : 135-146 share record
persistent URL:
Nachshon Cohen , Zeev Nutov : A (1 + ln 2)-Approximation Algorithm for Minimum-Cost 2-Edge-Connectivity Augmentation of Trees with Constant Radius. APPROX-RANDOM 2011 : 147-157 share record
persistent URL:
Michael S. Crouch , Andrew McGregor : Periodicity and Cyclic Shifts via Linear Sketches. APPROX-RANDOM 2011 : 158-170 export record
dblp key:
conf/approx/Dachman-SoledS11 share record
persistent URL:
Dana Dachman-Soled , Rocco A. Servedio : A Canonical Form for Testing Boolean Function Properties. APPROX-RANDOM 2011 : 460-471 share record
persistent URL:
Varsha Dani , Cristopher Moore : Independent Sets in Random Graphs from the Weighted Second Moment Method. APPROX-RANDOM 2011 : 472-482 share record
persistent URL:
Anindya De , Thomas Watson : Extractors and Lower Bounds for Locally Samplable Sources. APPROX-RANDOM 2011 : 483-494 export record
dblp key:
conf/approx/DellamonicaKMRS11 share record
persistent URL:
Domingos Dellamonica Jr. , Subrahmanyam Kalyanasundaram , Daniel M. Martin , Vojtech Rödl , Asaf Shapira : A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma. APPROX-RANDOM 2011 : 495-506 share record
persistent URL:
Irit Dinur , Tali Kaufman : Dense Locally Testable Codes Cannot Have Constant Rate and Distance. APPROX-RANDOM 2011 : 507-518 share record
persistent URL:
Feodor F. Dragan , Ekkehard Köhler : An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs. APPROX-RANDOM 2011 : 171-183 share record
persistent URL:
Andrew Drucker : Efficient Probabilistically Checkable Debates. APPROX-RANDOM 2011 : 519-529