東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

On the design and worst-case analysi...

Mao, Jia.

Linked to FindBook

Google Book

Amazon

博客來

On the design and worst-case analysis of certain interactive and approximation algorithms.

Record Type:	Language materials, printed : Monograph/item
Title/Author:	On the design and worst-case analysis of certain interactive and approximation algorithms./
Author:	Mao, Jia.
Description:	126 p.
Notes:	Adviser: Ronald L. Graham.
Contained By:	Dissertation Abstracts International67-12B.
Subject:	Canadian Studies. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3244382

On the design and worst-case analysis of certain interactive and approximation algorithms.
Mao, Jia.

On the design and worst-case analysis of certain interactive and approximation algorithms. - 126 p.

Adviser: Ronald L. Graham.

Thesis (Ph.D.)--University of California, San Diego, 2007.

With the speed of current technological changes, computation models are evolving to become more interactive and dynamic. These computation models often differ from traditional ones in that not every piece of the information needed for decision making is available a priori. Efficient algorithm design to solve these problems poses new challenges.Subjects--Topical Terms:

1020605
Canadian Studies.

On the design and worst-case analysis of certain interactive and approximation algorithms.
LDR:03159nam 2200301 a 45 001 941679
005 20110519
008 110519s2007 ||||||||||||||||| ||eng d
035 $a (UMI)AAI3244382
035 $a AAI3244382
040 $a UMI $c UMI
100 1 $a Mao, Jia. $3 1265775
245 1 0 $a On the design and worst-case analysis of certain interactive and approximation algorithms.
300 $a 126 p.
500 $a Adviser: Ronald L. Graham.
500 $a Source: Dissertation Abstracts International, Volume: 67-12, Section: B, page: 7170.
502 $a Thesis (Ph.D.)--University of California, San Diego, 2007.
520 $a With the speed of current technological changes, computation models are evolving to become more interactive and dynamic. These computation models often differ from traditional ones in that not every piece of the information needed for decision making is available a priori. Efficient algorithm design to solve these problems poses new challenges.
520 $a In this work we present and study some interactive and dynamic computations and design efficient algorithmic schemes to solve them. Our approach for performance evaluation falls within the framework of worst-case analysis. The worst-case scenarios are analyzed through the incorporation of imaginary adversaries or adversarial input sequences. Worst-case analysis provides safe performance guarantees even when we have little or no prior knowledge about the input sequences. Another natural yet powerful tool we utilize is an auxiliary graph which evolves as the computation progresses. It helps us to visualize the computation step by step, and more importantly, offers us powerful mathematical tools from the well-developed area of graph theory.
520 $a We first address a particular computation problem of interactive nature, best known as the Majority/Plurality game. This interactive game has appeared in several different contexts since the 1980s such as system diagnosis and group testing. We design and analyze optimal strategies to minimize the amount of communication needed in different settings against an imaginary adversary. We also consider error-tolerance features to make our strategies robust even in the presence of communication errors.
520 $a We then introduce a new variant of the classical bin packing problem that allows arbitrary splitting of the items with the restriction on the number of different types in each bin. This problem is specifically motivated by a practical problem of allocating memories to parallel processors in high-speed routers. It is also natural to other similar resource allocation applications. Even the simplest case of this problem can be shown to be NP-hard. We design efficient approximation algorithms in the offline, online, and dynamic settings. We also use an interesting epsilon-improvement technique to show improved approximation ratios.
590 $a School code: 0033.
650 4 $a Canadian Studies. $3 1020605
650 4 $a Computer Science. $3 626642
690 $a 0385
690 $a 0984
710 2 $a University of California, San Diego. $3 1018093
773 0 $t Dissertation Abstracts International $g 67-12B.
790 $a 0033
790 1 0 $a Graham, Ronald L., $e advisor
791 $a Ph.D.
792 $a 2007
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3244382