Approximation, randomization, and combinatorial optimization : algorithms and techniques : 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Appr

This Book Constitutes The Joint Refereed Proceedings Of The 4th International Workshop On Approximation Algorithms For Optimization Problems, Approx 2001 And Of The 5th International Workshop On Ranomization And Approximation Techniques In Computer Science, Random 2001, Held In Berkeley, California, Usa In August 2001. The 26 Revised Full Papers Presented Were Carefully Reviewed And Selected From A Total Of 54 Submissions. Among The Issues Addressed Are Design And Analysis Of Approximation Algorithms, Inapproximability Results, On-line Problems, Randomization, De-randomization, Average-case Analysis, Approximation Classes, Randomized Complexity Theory, Scheduling, Routing, Coloring, Partitioning, Packing, Covering, Computational Geometry, Network Design, And Applications In Various Fields. Invited Talks -- Using Complex Semidefinite Programming For Approximating Max E2-lin3 -- Hill-climbing Vs. Simulated Annealing For Planted Bisection Problems -- Web Search Via Hub Synthesis -- Error-correcting Codes And Pseudorandom Projections -- Order In Pseudorandomness -- Contributed Talks Of Approx -- Minimizing Stall Time In Single And Parallel Disk Systems Using Multicommodity Network Flows -- On The Equivalence Between The Primal-dual Schema And The Local-ratio Technique -- Online Weighted Flow Time And Deadline Scheduling -- An Online Algorithm For The Postman Problem With A Small Penalty -- A Simple Dual Ascent Algorithm For The Multilevel Facility Location Problem -- Approximation Schemes For Ordered Vector Packing Problems -- Incremental Codes -- A 3/2-approximation Algorithm For Augmenting The Edge-connectivity Of A Graph From 1 To 2 Using A Subset Of A Given Edge Set -- Approximation Algorithms For Budget-constrained Auctions -- Minimizing Average Completion Of Dedicated Tasks And Interval Graphs -- A Greedy Facility Location Algorithm Analyzed Using Dual Fitting -- 0.863-approximation Algorithm For Max Dicut -- The Maximum Acyclic Subgraph Problem And Degree-3 Graphs -- Some Approximation Results For The Maximum Agreement Forest Problem -- Contributed Talks Of Random -- Near-optimum Universal Graphs For Graphs With Bounded Degrees -- On A Generalized Ruin Problem -- On The B-partite Random Asymmetric Traveling Salesman Problem And Its Assignment Relaxation -- Exact Sampling In Machine Scheduling Problems -- On Computing Ad-hoc Selective Families -- L Infinity Embeddings -- On Euclidean Embeddings And Bandwidth Minimization -- The Non-approximability Of Non-boolean Predicates -- On The Derandomization Of Constant Depth Circuits -- Testing Parenthesis Languages -- Proclaiming Dictators And Juntas Or Testing Boolean Formulae -- Equitable Coloring Extends Chernoff-hoeffding Bounds. Edited By Michel Goemans, Klaus Jansen, José D. P. Rolim, Luca Trevisan. front-matter 1 Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques 3 Foreword 5 Table of Contents 7 fulltext 10 fulltext_001 11 fulltext_002 15 fulltext_003 16 fulltext_004 19 fulltext_005 21 Introduction 21 Modeling IPCxspace by Network Flows 23 The Network 23 Properties of Optimal Flows 25 Applying the Approximation Algorithm 26 Generalization to Multiple Disks 28 Improving the Approximation Factor 28 Bundling Intervals 28 Achieving the $(2D/z)$-Approximation 31 fulltext_006 34 Introduction 34 Definitions 36 Local-Ratio 37 Primal-Dual 38 Equivalence 41 Examples 42 fulltext_007 47 Introduction 47 Resource Augmentation Analysis of $P | r_i, pmtn | DOTSB sum @ slimits @ w_i F_i$ 49 Deadline Scheduling Problem 51 Conclusions 58 fulltext_008 59 Introduction 59 General Definitions 60 An Algorithm for the Corridor Model with a Penalty at Most $2|V|-2$ 61 Lowerbounds for the Corridor Model and the Labyrinth Model 63 Conclusions 64 fulltext_009 66 Introduction 66 The Metric Multilevel Uncapacitated Facility Location Problem 67 The Primal-Dual Algorithm 68 A Capacitated Version 72 fulltext_010 75 Introduction 75 An APTAS for the Ordered VP 79 Enumerating Packings for the Large Items 79 Packing the Small Items 81 Rounding the LP Solution for the General Dimension 82 Extension to Bounded Dilworth Number 85 fulltext_011 88 Motivating Example 88 General Notion and Construction 89 Optimal Code for $[0,1]$ 92 Hamming Space (Error-Correcting Codes) 94 Optimal $1$-Competitive Code for Hamming Space $F^n$, $|F|ge n$ 95 First Look at Small Alphabets 96 Algebraic-Geometric Codes 97 Concatenation Theorem 98 Random Linear Codes 100 Conclusions 102 fulltext_012 104 Introduction 104 Preliminaries 105 Motivation: A $2$-Approximation Algorithm 107 Lower Bound and the Credit Scheme 109 Two Special Small Trees 110 Matchings 111 A $3/2$-Approximation Algorithm 112 The Coupon Scheme 112 Algorithm Techniques 113 fulltext_013 116 Introduction 116 Paper Outline 118 Our Algorithm 118 Obtaining Simple Solutions 120 Indirect Purchase 120 Cycle Elimination 121 Item Exchanges 122 Bidder Exchanges 122 Correctness and Performance 123 Hardness of BCAP 125 fulltext_014 128 Introduction 128 Approximating Waiting Time and Throughput of Interval and Comparability Graphs 131 Scheduling Dedicated Tasks 136 fulltext_015 141 Introduction 141 The Algorithm 143 Analysis of the Algorithm 145 Running Time Analysis 147 Experimental Results 148 Variants 148 fulltext_016 152 Introduction 152 Semi-definite Programming Relaxation 153 Hyperplane Separation by Skewed Distributionhfill penalty -@M on Sphere 155 Main Theorem 156 Numerical Method for Designing Algorithm 158 Conclusion 159 fulltext_017 161 Introduction 161 Combinatorial Approximation Algorithms 162 An $frac {8}{9}$-Approximation 162 An $frac {11}{12}$-Approximation 165 A Lower Bound 167 Bounded-Degree Graphs 167 Reduction to Eulerian Graphs 167 Reduction to 3-Regular Graphs 169 fulltext_018 173 Introduction 173 Basic Definitions 174 Restrictions and Agreement Forests 174 Links 175 Eliminations 176 Algorithms 176 Operations 177 Cases and Transactions 178 Algorithms 1 and 2 179 Approximation Ratio 180 Barriers 180 Credits and Debits 181 An Upper Bound for the Approximation Ratio of Algorithm 2 182 A Lower Bound for the Approximation Ratio of Algorithm 1 182 Final Remarks 183 fulltext_019 184 Introduction and Main Result 184 A Graph Embedding Technique 186 Windmill Decomposition of Graphs 189 Universal Graphs with Fewer Vertices 191 More Details for Section 3 191 fulltext_020 195 Introduction 195 Notations 196 Upper Bound Analysis 198 Lower Bound Analysis 202 Concluding Remarks 203 fulltext_021 206 Introduction 206 Preliminaries 208 Proofs 208 Open Problems 215 fulltext_022 216 Introduction 216 Problem Definition 217 Applying CFTP to Our Scheduling Problems 218 Coupling the Evolution of Different States 218 Monotonicity of the Coupled Markov Chain 219 Running Time Analysis 220 Extensions 221 Simulation Results 221 fulltext_023 225 Introduction 225 Efficient Construction of Ad-hoc Selective Families 229 Two Applications of Theorem T @ref {thm::global-sel} 232 Hardness Results 234 Open Problems 236 fulltext_024 237 Introduction 237 Notation 237 Outline of Construction 237 Construction 238 Relation to Embeddings 241 fulltext_025 243 Introduction 243 Euclidean Embeddings of Metrics 244 A Semi-Definite Relaxation 245 A Rounding Algorithm 246 A Lower Bound on Volume Distortion 247 Embeddings Preserving Point-to-Subset Distances 249 The Embedding 250 The Proof 251 Convexity of $k^{th}$ Moments 252 Conclusion 254 fulltext_026 255 Introduction 255 Outline of the Construction 257 The PCP 259 The Reduction to Non-Boolean CSPs 260 Conclusions 261 fulltext_027 264 Introduction 264 Background 264 Our Results 265 Our Approach 265 Comparison with Previous Results 266 Organization 266 Preliminaries 267 Mild Hardness via Voting Polynomials 267 Extreme Hardness via Hard-Core Sets 269 Hard-Core Sets for Constant Depth Circuits 270 Amplifying Hardness with the XOR Lemma 271 Approximate Majority and Uniform Circuit Constructions 272 Conclusion 273 Proof of Lemma T @ref {lem:term} 274 fulltext_028 276 Introduction 276 Preliminaries 278 The Algorithm for Testing $D_m$ 280 Checking Consistency 280 A Preprocessing Stage 280 Obtaining Estimates of Excess numbers 281 The Matching Graph 282 Matching between Neighbors 284 Putting It All Together 286 fulltext_029 288 Introduction 288 Our Results 290 Related Work 290 Preliminaries 292 Testing Singletons 292 Testing Monomials 295 Testing Monotone DNF Formulae 296 fulltext_030 301 Introduction 301 Proof of the Main Theorem 305 Sharper Bounds in Special Cases 309 Conclusions 311 back-matter 313 Author Index 313 Using Complex Semidefinite Programming for Approximating MAX E2-LIN3....Pages 1-1 Hill-Climbing vs. Simulated Annealing for Planted Bisection Problems....Pages 2-5 Web Search via Hub Synthesis....Pages 6-6 Error-Correcting Codes and Pseudorandom Projections....Pages 7-9 Order in Pseudorandomness....Pages 10-11 Minimizing Stall Time in Single and Parallel Disk Systems Using Multicommodity Network Flows....Pages 12-24 On the Equivalence between the Primal-Dual Schema and the Local-Ratio Technique....Pages 24-36 Online Weighted Flow Time and Deadline Scheduling....Pages 36-47 An Online Algorithm for the Postman Problem with a Small Penalty....Pages 48-54 A Simple Dual Ascent Algorithm for the Multilevel Facility Location Problem....Pages 55-63 Approximation Schemes for Ordered Vector Packing Problems....Pages 63-75 Incremental Codes....Pages 75-90 A 3/2-Approximation Algorithm for Augmenting the Edge-Connectivity of a Graph from 1 to 2 Using a Subset of a Given Edge Set....Pages 90-101 Approximation Algorithms for Budget-Constrained Auctions....Pages 102-113 Minimizing Average Completion of Dedicated Tasks and Interval Graphs....Pages 114-126 A Greedy Facility Location Algorithm Analyzed Using Dual Fitting....Pages 127-137 0.863-Approximation Algorithm for MAX DICUT....Pages 138-146 The Maximum Acyclic Subgraph Problem and Degree-3 Graphs....Pages 147-158 Some Approximation Results for the Maximum Agreement Forest Problem....Pages 159-169 Near-optimum Universal Graphs for Graphs with Bounded Degrees....Pages 170-180 On a Generalized Ruin Problem....Pages 181-191 On the b -Partite Random Asymmetric Traveling Salesman Problem and Its Assignment Relaxation....Pages 192-201 Exact Sampling in Machine Scheduling Problems....Pages 202-210 On Computing Ad-hoc Selective Families....Pages 211-222 L Infinity Embeddings....Pages 223-228 On Euclidean Embeddings and Bandwidth Minimization....Pages 229-240 The Non-approximability of Non-Boolean Predicates....Pages 241-249 On the Derandomization of Constant Depth Circuits....Pages 249-260 Testing Parenthesis Languages....Pages 261-272 Proclaiming Dictators and Juntas or Testing Boolean Formulae....Pages 273-285 Equitable Coloring Extends Chernoff-Hoeffding Bounds....Pages 285-296 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.