LEADER 06453nam 22008655 450 001 9910143893203321 005 20251116234255.0 010 $a3-540-45753-4 024 7 $a10.1007/3-540-45753-4 035 $a(CKB)1000000000211850 035 $a(SSID)ssj0000321373 035 $a(PQKBManifestationID)11241019 035 $a(PQKBTitleCode)TC0000321373 035 $a(PQKBWorkID)10264104 035 $a(PQKB)10749721 035 $a(DE-He213)978-3-540-45753-4 035 $a(MiAaPQ)EBC3072072 035 $a(PPN)155177710 035 $a(BIP)7933782 035 $a(EXLCZ)991000000000211850 100 $a20121227d2002 u| 0 101 0 $aeng 135 $aurnn|008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aApproximation Algorithms for Combinatorial Optimization $e5th International Workshop, APPROX 2002, Rome, Italy, September 17-21, 2002. Proceedings /$fedited by Klaus Jansen, Stefano Leonardi, Vijay Vazirani 205 $a1st ed. 2002. 210 1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d2002. 215 $a1 online resource (VIII, 276 p.) 225 1 $aLecture Notes in Computer Science,$x1611-3349 ;$v2462 300 $aBibliographic Level Mode of Issuance: Monograph 311 08$a3-540-44186-7 320 $aIncludes bibliographical references and index. 327 $aSearch and Classification of High Dimensional Data -- Bicriteria Spanning Tree Problems -- Improved Approximation Algorithms for Multilevel Facility Location Problems -- On Constrained Hypergraph Coloring and Scheduling -- On the Power of Priority Algorithms for Facility Location and Set Cover -- Two Approximation Algorithms for 3-Cycle Covers -- Approximation Algorithms for the Unsplittable Flow Problem -- 1.5-Approximation for Treewidth of Graphs Excluding a Graph with One Crossing as a Minor -- Typical Rounding Problems -- Approximating Min-sum Set Cover -- Approximating Maximum Edge Coloring in Multigraphs -- Approximating the Complement of the Maximum Compatible Subset of Leaves of k Trees -- A 27/26-Approximation Algorithm for the Chromatic Sum Coloring of Bipartite Graphs -- Facility Location and the Geometric Minimum-Diameter Spanning Tree -- Improved Approximation Algorithms for the Partial Vertex Cover Problem -- Minimum Restricted Diameter Spanning Trees -- Hardness of Approximation for Vertex-Connectivity Network-Design Problems -- Non-abusiveness Helps: An % MathType!MTEF!2!1!+- % feaafiart1ev1aaatCvAUfKttLearuqr1ngBPrgarmWu51MyVXgatC % vAUfeBSjuyZL2yd9gzLbvyNv2CaeHbuLwBLnhiov2DGi1BTfMBaeHb % d9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbb % L8F4rqqrFfpeea0xe9Lq-Jc9vqaqpepm0xbba9pwe9Q8fs0-yqaqpe % pae9pg0FirpepeKkFr0xfr-xfr-xb9adbaqaaeGaciGaaiaadeWaaq % aadaqbaaGcbaGaaGOmamaaCaaaleqabaGagiiBaWMaei4Ba8Maei4z % aCgaaOWaaWbaaSqabeaadaahaaadbeqaamaaBaaabaWaaWbaaeqaba % GaaGymaiabgkHiTiabgIGiodaaaeqaaaaaaaGcdaahaaWcbeqaaiab % d6gaUbaaaaa!4546! \[ 2^{\log } ^{^{_{^{1 - \in } } } } ^n \] (1)-Competitive Algorithm for Minimizing the Maximum Flow Time in the Online Traveling Salesman Problem -- Routing and Admission Control in Networks with Advance Reservations -- Improved Approximation Algorithms for Metric Facility Location Problems -- Complexity of Makespan Minimization for Pipeline Transportation of Petroleum Products -- Primal-Dual Algorithms for Connected Facility Location Problems. 330 $aThe Workshop on Approximation Algorithms for Combinatorial Optimization Problems APPROX 2002 focused on algorithmic and complexity aspects ar- ing in the development of e'cient approximate solutions to computationally d- ?cult problems. It aimed, in particular, to foster cooperation among algorithmic and complexity researchers in the ?eld. The workshop, held at the University of Rome La Sapienza, Rome, Italy, was part of the ALGO 2002 event, in conju- tion with ESA 2002 and WABI 2002. We would like to thank the local organizers at the University of Rome La Sapienza for this opportunity. APPROX is an - nual meeting, with previous workshops in Aalborg, Berkeley, Saarbruc ¨ ken, and Berkeley. Previous proceedings appeared as LNCS 1444, 1671, 1913, and 2129. Topics of interest for APPROX 2002 were: design and analysis of approxi- tion algorithms, inapproximability results, on-line problems, randomization te- niques, average-case analysis, approximation classes, scheduling problems, ro- ing and ?ow problems, coloring and partitioning, cuts and connectivity, packing and covering, geometric problems, network design, applications to game theory, and other applications. The number of submitted papers to APPROX 2002 was 54 from which 20 papers were selected. This volume contains the selected papers together with abstracts of invited lectures by Yuval Rabani (Technion) and R. 410 0$aLecture Notes in Computer Science,$x1611-3349 ;$v2462 606 $aComputer programming 606 $aComputer science 606 $aMathematical optimization 606 $aAlgorithms 606 $aComputer science?Mathematics 606 $aDiscrete mathematics 606 $aNumerical analysis 606 $aProgramming Techniques 606 $aTheory of Computation 606 $aOptimization 606 $aAlgorithms 606 $aDiscrete Mathematics in Computer Science 606 $aNumerical Analysis 615 0$aComputer programming. 615 0$aComputer science. 615 0$aMathematical optimization. 615 0$aAlgorithms. 615 0$aComputer science?Mathematics. 615 0$aDiscrete mathematics. 615 0$aNumerical analysis. 615 14$aProgramming Techniques. 615 24$aTheory of Computation. 615 24$aOptimization. 615 24$aAlgorithms. 615 24$aDiscrete Mathematics in Computer Science. 615 24$aNumerical Analysis. 676 $a004/.01/51 702 $aJansen$b Klaus$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aLeonardi$b Stefano$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aVazirani$b Vijay$4edt$4http://id.loc.gov/vocabulary/relators/edt 712 12$aInternational Workshop on Approximation Algorithms for Combinatorial Optimization Problems 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910143893203321 996 $aApproximation Algorithms for Combinatorial Optimization$92209915 997 $aUNINA