Lecture Notes in Computer Science 5171 CommencedPublicationin1973 FoundingandFormerSeriesEditors: GerhardGoos,JurisHartmanis,andJanvanLeeuwen EditorialBoard DavidHutchison LancasterUniversity,UK TakeoKanade CarnegieMellonUniversity,Pittsburgh,PA,USA JosefKittler UniversityofSurrey,Guildford,UK JonM.Kleinberg CornellUniversity,Ithaca,NY,USA AlfredKobsa UniversityofCalifornia,Irvine,CA,USA FriedemannMattern ETHZurich,Switzerland JohnC.Mitchell StanfordUniversity,CA,USA MoniNaor WeizmannInstituteofScience,Rehovot,Israel OscarNierstrasz UniversityofBern,Switzerland C.PanduRangan IndianInstituteofTechnology,Madras,India BernhardSteffen UniversityofDortmund,Germany MadhuSudan MassachusettsInstituteofTechnology,MA,USA DemetriTerzopoulos UniversityofCalifornia,LosAngeles,CA,USA DougTygar UniversityofCalifornia,Berkeley,CA,USA GerhardWeikum Max-PlanckInstituteofComputerScience,Saarbruecken,Germany Ashish Goel Klaus Jansen José D.P. Rolim Ronitt Rubinfeld (Eds.) Approximation, Randomization and Combinatorial Optimization Algorithms and Techniques 11th International Workshop, APPROX 2008 and12thInternationalWorkshop,RANDOM2008 Boston, MA, USA, August 25-27, 2008 Proceedings 1 3 VolumeEditors AshishGoel StanfordUniversity,DepartmentofManagementScienceandEngineering and(bycourtesy)ComputerScience Terman311,Stanford,CA,94305, USA E-mail:[email protected] KlausJansen UniversityofKiel,InstituteforComputerScience Olshausenstrasse40,24118Kiel,Germany E-mail:[email protected] JoséD.P.Rolim CentreUniversitaired’Informatique,BattelleBâtimentA RoutedeDrize7,1227Carouge,Geneva,Switzerland E-mail:[email protected] RonittRubinfeld MassachusettsInstituteofTechnology ComputerScienceandArtificialIntelligenceLaboratory 32VassarStreet,Building32-G698,Cambridge,MA02139,USA E-mail:[email protected] LibraryofCongressControlNumber:2008933319 CRSubjectClassification(1998):F.2,G.2,G.1 LNCSSublibrary:SL1–TheoreticalComputerScienceandGeneralIssues ISSN 0302-9743 ISBN-10 3-540-85362-6SpringerBerlinHeidelbergNewYork ISBN-13 978-3-540-85362-6SpringerBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violationsareliable toprosecutionundertheGermanCopyrightLaw. SpringerisapartofSpringerScience+BusinessMedia springer.com ©Springer-VerlagBerlinHeidelberg2008 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper SPIN:12456543 06/3180 543210 Preface This volume contains the papers presented at the 11th International Work- shop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2008) and the 12th International Workshop on Randomization and Computation(RANDOM2008),whichtookplaceconcurrentlyattheMIT(Mas- sachusetts Institute of Technology) in Boston, USA, during August 25–27,2008.APPROXfocusesonalgorithmicandcomplexityissuessurrounding the development of efficient approximate solutions to computationally difficult problems, and was the 11th in the series after Aalborg (1998), Berkeley (1999), Saarbru¨cken(2000),Berkeley(2001),Rome(2002),Princeton(2003),Cambridge (2004), Berkeley (2005), Barcelona (2006), and Princeton (2007). RANDOM is concernedwith applications of randomnessto computational and combinatorial problems, and was the 12th workshop in the series following Bologna (1997), Barcelona (1998), Berkeley (1999), Geneva (2000), Berkeley (2001), Harvard (2002),Princeton(2003),Cambridge(2004),Berkeley(2005),Barcelona(2006), and Princeton (2007). TopicsofinterestforAPPROXandRANDOMare:designandanalysisofap- proximationalgorithms,hardnessofapproximation,smallspace,sub-lineartime, streaming, algorithms, embeddings and metric space methods, mathematical programmingmethods,combinatorialproblemsingraphsandnetworks,gamethe- ory, markets, economic applications, geometric problems, packing, covering, scheduling,approximatelearning,designandanalysisofrandomizedalgorithms, randomizedcomplexitytheory,pseudorandomnessandderandomization,random combinatorial structures, random walks/Markov chains, expander graphs and randomnessextractors,probabilisticproofsystems,randomprojectionsandem- beddings,error-correctingcodes,average-caseanalysis,propertytesting,compu- tationallearningtheory,andotherapplicationsofapproximationandrandomness. The volume contains 20 contributed papers, selected by the APPROX Pro- gram Committee out of 42 submissions, and 27 contributed papers, selected by the RANDOM ProgramCommittee out of 50 submissions. We would like to thank all of the authors who submitted papers and the members of the ProgramCommittees: APPROX 2008 Matthew Andrews, Bell Labs Timothy Chan, University of Waterloo Julia Chuzhoy, Toyota Technological Institute at Chicago Uriel Feige, Weizmann Institute Ashish Goel, Stanford University (Chair) VI Preface Elad Hazan, IBM Almaden Research Center Stefano Leonardi, Sapienza University of Rome Aranyak Mehta, Georgia Institute of Technology Vahab Mirrokni, Massachusetts Institute of Technology Kamesh Munagala, Duke University Adi Rosen, Laboratoire de Recherche en Informatique David Shmoys, Cornell University Adrian Vetta, McGill University Jan Vondrak, Princeton University David Williamson, Cornell University RANDOM 2008 Nir Ailon, Google Research Tugkan Batu, University of Pennsylvania Petra Berenbrink, Simon Fraser University Harry Buhrman, University of Amsterdam Amin Coja-Oghlan,University of Edinburgh Anna Gal, University of Chicago Yuval Ishai, Technion-IsraelInstitute of Technology David Kempe, University of Southern California Adam Klivans, University of Texas at Austin Ronitt Rubinfeld, Massachusetts Institute of Technology (Chair) Alex Samorodnitsky, The Hebrew University of Jerusalem Martin Strauss, University of Michigan Amir Shpilka, Technion-IsraelInstitute of Technology Eric Vigoda, Georgia Institute of Technology David Woodruff, IBM Almaden Research Center We would also like to thank the external subreferees: Scott Aaronson, Alexandr Andoni, Nikhil Bansal, Boaz Barak, Omer Barkol, Luca Becchetti, Eli Ben-Sasson, Petra Berenbrink, Ivona Bezakova, Julia Boettcher, Andrej Bogdanov, Vincenzo Bonifaci, Chandra Chekuri, Zhi-Zhong Chen, Ken Clarkson, Colin Cooper, Mary Cryan, Artur Czumaj, Anirban Das- gupta, Ned Dimitrov, Irit Dinur, Debora Donato, Petros Drineas, Philippe Duchon, Michael Elkin, Robert Elsaesser, Funda Ergun, Vitaly Feldman, El- darFischer,ThomasFriedetzky,ToshihiroFujito,KonstantinosGeorgiou,Anna Gilbert, Andreas Goerdt, Fabrizio Grandoni, Dan Gutfreund, Prahladh Harsha,Piotr Indyk, Kazuo Iwama,SatyenKale,Mihyun Kang,Adriana Kara- giozova, Marek Karpinski, Iordanis Kerenidis, Sanjeev Khanna, Guy Kindler, Swastik Kopparty, James Lee, Troy Lee, David Liben-Nowell, Satya Lokam, Shachar Lovett, Mohammad Mahdian, Konstantin Makarychev, Russell Mar- tin, Arie Matsliah, Dieter van Melkebeek, Daniele Micciancio, Alantha New- man,OferNeiman,RolfNiedermeier,JelaniNelson,JeffPhillips,YuvalRabani, LuisRademacher,AnupRao,RanRaz,BruceReed,OdedRegev,HeikoRoglin, Preface VII Dana Ron, Mark Rudelson, Atri Rudra, Matthias Ruhl, Tamas Sarlos, Thomas Sauerwald, Gabriel Scalosub, Mathias Schacht, Christian Schaffner, Christian Scheideler, Florian Schoppmann, C. Seshadhri, Ronen Shaltiel, Asaf Shapira, AlexanderSherstov,AnastosiosSidiroupoulos,ShakharSmorodinsky,SagiSnir, Christian Sohler, Xiaoming Sun, Maxim Sviridenko, Chaitanya Swamy, Mario Szegedy, Kunal Talwar, Anush Taraz, Iannis Tourlakis, Chris Umans, Falk Unger,PaulValiant,SantoshVempala,DannyVilenchik,EmanueleViola,Tandy Warnow, Enav Weinreb, Udi Wieder, Sergey Yekhanin, Yitong Yin, Shengyu Zhang, David Zuckerman, and Hamid Zarrabi-Zadeh. We gratefully acknowledge the support from Microsoft Research, the De- partment of Management Science and Engineering of Stanford University, the DepartmentofElectricalEngineeringandComputerScienceandtheLaboratory for Computer Science and Artificial Intelligence at the Massachusetts Institute of Technology, the Institute of Computer Science of the Christian-Albrechts- Universita¨t zu Kiel and the Department of Computer Science of the University of Geneva. August 2008 Ashish Goel Ronitt Rubinfeld Klaus Jansen Jos´e D.P. Rolim Table of Contents Contributed Talks of APPROX Approximating Optimal Binary Decision Trees....................... 1 Micah Adler and Brent Heeringa Santa Claus Meets Hypergraph Matchings .......................... 10 Arash Asadpour, Uriel Feige, and Amin Saberi Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction....................................................... 21 Mihai Ba˘doiu, Erik D. Demaine, MohammadTaghi Hajiaghayi, Anastasios Sidiropoulos, and Morteza Zadimoghaddam Connected Vertex Covers in Dense Graphs .......................... 35 Jean Cardinal and Eythan Levy Improved Approximation Guarantees through Higher Levels of SDP Hierarchies...................................................... 49 Eden Chlamtac and Gyanit Singh Sweeping Points ................................................. 63 Adrian Dumitrescu and Minghui Jiang Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness............................ 77 Venkatesan Guruswami and Prasad Raghavendra Fully PolynomialTime ApproximationSchemes for Time-CostTradeoff Problems in Series-ParallelProject Networks ........................ 91 Nir Halman, Chung-Lun Li, and David Simchi-Levi Efficient Algorithms for Fixed-Precision Instances of Bin Packing and Euclidean TSP .................................................. 104 David R. Karger and Jacob Scott Approximating Maximum Subgraphs without Short Cycles............ 118 Guy Kortsarz, Michael Langberg, and Zeev Nutov Deterministic 7/8-Approximationfor the Metric Maximum TSP ....... 132 L(cid:2) ukasz Kowalik and Marcin Mucha Inapproximability of Survivable Networks ........................... 146 Yuval Lando and Zeev Nutov X Table of Contents Approximating Single Machine Scheduling with Scenarios ............. 153 Monaldo Mastrolilli, Nikolaus Mutsanas, and Ola Svensson Streaming Algorithms for k-Center Clustering with Outliers and with Anonymity...................................................... 165 Richard Matthew McCutchen and Samir Khuller A General Framework for Designing Approximation Schemes for CombinatorialOptimizationProblemswithManyObjectivesCombined into One ........................................................ 179 Shashi Mittal and Andreas S. Schulz The Directed Minimum Latency Problem ........................... 193 Viswanath Nagarajan and R. Ravi A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem ........................................................ 207 Tha`nh Nguyen Approximating Directed Weighted-Degree Constrained Networks....... 219 Zeev Nutov A Constant Factor Approximation for Minimum λ-Edge-Connected k-Subgraph with Metric Costs ..................................... 233 MohammadAli Safari and Mohammad R. Salavatipour Budgeted Allocations in the Full-Information Setting ................. 247 Aravind Srinivasan Contributed Talks of RANDOM Optimal Random Matchings on Trees and Applications ............... 254 Jeff Abrahamson, B´ela Csaba, and Ali Shokoufandeh Small Sample Spaces Cannot Fool Low Degree Polynomials ........... 266 Noga Alon, Ido Ben-Eliezer, and Michael Krivelevich Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size ............................................................ 276 V. Arvind and Partha Mukhopadhyay Tensor Products of Weakly Smooth Codes Are Robust................ 290 Eli Ben-Sasson and Michael Viderman On the Degree Sequences of Random Outerplanar and Series-Parallel Graphs ......................................................... 303 Nicla Bernasconi, Konstantinos Panagiotou, and Angelika Steger Improved Bounds for Testing Juntas................................ 317 Eric Blais Table of Contents XI The Complexity of Distinguishing Markov Random Fields............. 331 Andrej Bogdanov, Elchanan Mossel, and Salil Vadhan Reconstruction of Markov Random Fields from Samples: Some Observations and Algorithms...................................... 343 Guy Bresler, Elchanan Mossel, and Allan Sly Tight Bounds for Hashing Block Sources............................ 357 Kai-Min Chung and Salil Vadhan Improved Separations between Nondeterministic and Randomized Multiparty Communication ....................................... 371 Matei David, Toniann Pitassi, and Emanuele Viola Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs ......................................... 385 Hang Dinh and Alexander Russell On the Query Complexity of Testing Orientations for Being Eulerian ... 402 Eldar Fischer, Oded Lachish, Ilan Newman, Arie Matsliah, and Orly Yahalom Approximately Counting Embeddings into Random Graphs ........... 416 Martin Fu¨rer and Shiva Prasad Kasiviswanathan Increasing the Output Length of Zero-ErrorDispersers ............... 430 Ariel Gabizon and Ronen Shaltiel Euclidean Sections of (cid:3)N with Sublinear Randomness and 1 Error-Correctionover the Reals.................................... 444 Venkatesan Guruswami, James R. Lee, and Avi Wigderson The Complexity of Local List Decoding............................. 455 Dan Gutfreund and Guy N. Rothblum Limitations of Hardness vs. Randomness under Uniform Reductions .... 469 Dan Gutfreund and Salil Vadhan Learning Random Monotone DNF ................................. 483 Jeffrey C. Jackson, Homin K. Lee, Rocco A. Servedio, and Andrew Wan Breaking the (cid:4)-Soundness Bound of the Linearity Test over GF(2)...... 498 Tali Kaufman, Simon Litsyn, and Ning Xie Dense Fast Random Projections and Lean Walsh Transforms .......... 512 Edo Liberty, Nir Ailon, and Amit Singer Near Optimal Dimensionality Reductions That Preserve Volumes ...... 523 Avner Magen and Anastasios Zouzias XII Table of Contents Sampling Hypersurfaces through Diffusion .......................... 535 Hariharan Narayanan and Partha Niyogi A 2-Source Almost-Extractor for Linear Entropy..................... 549 Anup Rao Extractors for Three Uneven-Length Sources ........................ 557 Anup Rao and David Zuckerman The Power of Choice in a Generalized Po´lya Urn Model............... 571 Gregory B. Sorkin Corruption and Recovery-EfficientLocally Decodable Codes........... 584 David Woodruff Quasi-randomness Is Determined by the Distribution of Copies of a Fixed Graph in Equicardinal Large Sets ............................ 596 Raphael Yuster Author Index.................................................. 603