東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Approximation algorithms for facilit...

Zhang, Jiawei.

Linked to FindBook

Google Book

Amazon

博客來

Approximation algorithms for facility location problems.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Approximation algorithms for facility location problems./
Author:	Zhang, Jiawei.
Description:	84 p.
Notes:	Source: Dissertation Abstracts International, Volume: 65-09, Section: B, page: 4808.
Contained By:	Dissertation Abstracts International65-09B.
Subject:	Operations Research. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3145587
ISBN:	0496045490

Approximation algorithms for facility location problems.
Zhang, Jiawei.

Approximation algorithms for facility location problems. - 84 p.

Source: Dissertation Abstracts International, Volume: 65-09, Section: B, page: 4808.

Thesis (Ph.D.)--Stanford University, 2004.

One of the most important aspects of logistics is to decide where to locate new facilities such as plants, distribution centers, and retailers. Facility location models not only have important applications in designing distribution systems, but also often form identifiable parts of other practical problems. However, many discrete location problems are NP-hard and the scale of the instances arising in practice is often too large to be solved optimally. In this thesis, we focus on polynomial time approximation algorithms for solving the well-known uncapacitated facility location problem and its generalizations.

ISBN: 0496045490Subjects--Topical Terms:

626629
Operations Research.

Approximation algorithms for facility location problems.
LDR:03102nmm 2200289 4500 001 1850445
005 20051208095320.5
008 130614s2004 eng d
020 $a 0496045490
035 $a (UnM)AAI3145587
035 $a AAI3145587
040 $a UnM $c UnM
100 1 $a Zhang, Jiawei. $3 1938370
245 1 0 $a Approximation algorithms for facility location problems.
300 $a 84 p.
500 $a Source: Dissertation Abstracts International, Volume: 65-09, Section: B, page: 4808.
500 $a Adviser: Yinyu Ye.
502 $a Thesis (Ph.D.)--Stanford University, 2004.
520 $a One of the most important aspects of logistics is to decide where to locate new facilities such as plants, distribution centers, and retailers. Facility location models not only have important applications in designing distribution systems, but also often form identifiable parts of other practical problems. However, many discrete location problems are NP-hard and the scale of the instances arising in practice is often too large to be solved optimally. In this thesis, we focus on polynomial time approximation algorithms for solving the well-known uncapacitated facility location problem and its generalizations.
520 $a In the uncapacitated problem, we are given a set of clients; a set of possible locations for facilities, the cost of opening a facility at each location, and the cost of connecting each client to a facility at each location. The objective is to open facilities at a subset of these locations, and connect each client to an open facility to minimize the sum of facility opening and connection costs. We assume that connection costs obey the triangle inequality. It is known that a 1.46-approximation algorithm for the uncapacitated problem would imply P = NP. In this thesis, we improve a long line of previous results and give a 1.52-approximation algorithm for the uncapacitated problem.
520 $a We also consider several important generalizations of the uncapacitated problem, including: (1) Capacitated facility location: Each facility can serve only a certain amount of clients. We present a multi-exchange local search algorithm for this problem. We show its approximation ratio is between 3 + 22 - epsilon and 3 + 22 + epsilon for any given constant epsilon > 0. (2) Multi-level facility location: The demands must be routed among the facilities in a hierarchical order. We give the best combinatorial algorithm for this problem. For the special case when there are only two levels of facilities, we give a 1.77-approximation algorithm, which is currently the best. (3) Dynamic facility location: The demand varies between time-periods. In addition to the question of where to locate facilities, this problem also addresses the question of when to locate them. We develop the first approximation algorithm for this problem.
590 $a School code: 0212.
650 4 $a Operations Research. $3 626629
690 $a 0796
710 2 0 $a Stanford University. $3 754827
773 0 $t Dissertation Abstracts International $g 65-09B.
790 1 0 $a Ye, Yinyu, $e advisor
790 $a 0212
791 $a Ph.D.
792 $a 2004
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3145587