逼近、随机化与组合优化：算法与技术Approximation,Randomization,and Combinatorial Optimization

逼近、随机化与组合优化：算法与技术Approximation,Randomization,and Combinatorial Optimization

分享

作者: Michel Goemans 著

出版社: Oversea Publishing House

出版时间: 2001-09

版次: 1

ISBN: 9783540424703

定价: 110.00

装帧: 平装

开本: 32开

纸张: 铜版纸

页数: 206页

分类: 外文古旧书>英文书>工程技术

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
内容简介:
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

查看详情

相关分类

Literature&Fiction文学与虚构 ScienceFiction&Fantasy科幻与玄幻 Romance浪漫小说 Mystery&Thrillers神秘与惊悚 Teens青少年读物 Biographies&Memoirs传记与自传 Comics&GraphicNovels动漫与绘画小说 ELT英语学习 Reference参考书 StandardTest标准考试 Business&Investing商业与投资 Self-Help励志自助 ManagementLeadership经营管理 Arts&Photography艺术与摄影

2

Approximation, Randomization and Combinatorial 【详见图】

九品

6969书店

北京市昌平区

平均发货5小时成功完成率97.56%

￥120.00

券

100减20

立即购买加入购物车不属于本条目