逼近、随机化与组合优化：算法与技术Approximation,Randomization,and Combinatorial Optimization
点此进入淘宝搜索页搜索分類: 图书,进口原版书,科学与技术 Science & Techology ,
作者： Michel Goemans 等著
出 版 社： Oversea Publishing House
出版时间： 2001-9-1字数：版次： 1页数： 206印刷时间： 2001/09/01开本： 32开印次： 1纸张： 铜版纸I S B N ： 9783540424703包装： 平装内容简介
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
Yevgeniy Dodis
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
Author Index
