Language:
English
繁體中文
Help
回圖書館首頁
手機版館藏查詢
Login
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
based on 0 review(s)
Location:
ALL
電子資源
Year:
Volume Number:
Items
1 records • Pages 1 •
1
Inventory Number
Location Name
Item Class
Material type
Call number
Usage Class
Loan Status
No. of reservations
Opac note
Attachments
W9261974
電子資源
11.線上閱覽_V
電子書
EB
一般使用(Normal)
On shelf
0
1 records • Pages 1 •
1
Multimedia
Reviews
Add a review
and share your thoughts with other readers
Export
pickup library
Processing
...
Change password
Login