東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Approximation Algorithms for Network...

Li, Shi.

Linked to FindBook

Google Book

Amazon

博客來

Approximation Algorithms for Network Routing and Facility Location Problems.

Record Type:	Language materials, printed : Monograph/item
Title/Author:	Approximation Algorithms for Network Routing and Facility Location Problems./
Author:	Li, Shi.
Description:	157 p.
Notes:	Source: Dissertation Abstracts International, Volume: 75-04(E), Section: B.
Contained By:	Dissertation Abstracts International75-04B(E).
Subject:	Computer Science. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3608331
ISBN:	9781303663703

Approximation Algorithms for Network Routing and Facility Location Problems.
Li, Shi.

Approximation Algorithms for Network Routing and Facility Location Problems. - 157 p.

Source: Dissertation Abstracts International, Volume: 75-04(E), Section: B.

Thesis (Ph.D.)--Princeton University, 2014.

We study approximation algorithms for two classes of optimization problems.

ISBN: 9781303663703Subjects--Topical Terms:

626642
Computer Science.

Approximation Algorithms for Network Routing and Facility Location Problems.
LDR:02400nam a2200313 4500 001 1966968
005 20141112075557.5
008 150210s2014 ||||||||||||||||| ||eng d
020 $a 9781303663703
035 $a (MiAaPQ)AAI3608331
035 $a AAI3608331
040 $a MiAaPQ $c MiAaPQ
100 1 $a Li, Shi. $3 2103875
245 1 0 $a Approximation Algorithms for Network Routing and Facility Location Problems.
300 $a 157 p.
500 $a Source: Dissertation Abstracts International, Volume: 75-04(E), Section: B.
500 $a Adviser: Moses Charikar.
502 $a Thesis (Ph.D.)--Princeton University, 2014.
520 $a We study approximation algorithms for two classes of optimization problems.
520 $a The first class is network routing problems. These are an important class of optimization problems, among which the edge-disjoint paths (EDP ) problem is one of the central and most extensively studied. In the first part of my thesis, I will give a poly-logarithmic approximation for EDP with congestion 2. This culminates a long line of research on the EDP with congestion problem.
520 $a The second class is facility location problems. Two important problems in this class are uncapacitated facility location (UFL) and k-median, both having long histories and numerous applications. We give improved approximation ratios for both problems in the second part of my thesis.
520 $a For UFL, we present a 1.488-approximation algorithm for the metric uncapacitated facility location (UFL) problem. The previous best algorithm, due to Byrka, gave a 1.5-approximation for UFL. His algorithm is parametrized by gamma whose value is set to a fixed number. We show that if gamma is randomly selected, the approximation ratio can be improved to 1.488.
520 $a For k-median, we present an improved approximation algorithm for k-median. Our algorithm, which gives a 1+ 3 + epsilon-approximation for k-median, is based on two rather surprising components. First, we show that it suffices to find an alpha-approximate solution that contains k+ O(1) medians. Second, we give such a pseudo-approximation algorithm with alpha =1+ 3 + epsilon.
590 $a School code: 0181.
650 4 $a Computer Science. $3 626642
690 $a 0984
710 2 $a Princeton University. $b Computer Science. $3 2099280
773 0 $t Dissertation Abstracts International $g 75-04B(E).
790 $a 0181
791 $a Ph.D.
792 $a 2014
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3608331