Approximation algorithms for combinatorial optimization : 5th International Workshop, APPROX 2002, Rome, Italy, September 17-21, 2002 : proceedings

Klaus Jansen, Stefano Leonardi, Vijay Vazirani (eds.)

This book constitutes the refereed proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002, held in Rome, Italy in September 2002. The 20 revised full papers presented were carefully reviewed and selected from 54 submissions. Among the topics addressed are design and analysis of approximation algorithms, inapproximability results, online problems, randomization techniques, average-case analysis, approximation classes, scheduling problems, routing and flow problems, coloring and partitioning, cuts and connectivity, packing and covering, geometric problems, network design, and applications to game theory and other fields.

「Nielsen BookData」より

[目次]

  • Search 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.

「Nielsen BookData」より

この本の情報

書名 Approximation algorithms for combinatorial optimization : 5th International Workshop, APPROX 2002, Rome, Italy, September 17-21, 2002 : proceedings
著作者等 Jansen, Klaus
Vazirani, Vijay V
Workshop on Approximation Algorithms for Combinatorial Optimization Problems
Leonardi Stefano
シリーズ名 Lecture notes in computer science
出版元 Springer
刊行年月 c2002
ページ数 viii, 269 p.
大きさ 24 cm
ISBN 3540441867
NCID BA58860697
※クリックでCiNii Booksを表示
言語 英語
出版国 ドイツ
この本を: 
このエントリーをはてなブックマークに追加

このページを印刷

外部サイトで検索

この本と繋がる本を検索

ウィキペディアから連想