Luận án tiến sĩ: Thiết kế thuật toán tương tác và xấp xỉ - Jia Mao

UNIVERSITY OF CALIFORNIA, SAN DIEGO On the Design and Worst-Case Analysis of Certain Interactive and Approximation Algorithms A dissertation submitted in partial satisfaction of the requirements for the degree Doctor of Philosophy in Computer Science by Jia Mao Committee in charge: Professor Ronald L. Graham, Chair Professor Samuel R. Buss Professor Fan Chung Graham Professor Alon Orlitsky Professor George Varghese 2007 UMI Number: 3244382 UMI Microform 3244382 Copyright 2007 by ProQuest Information and Learning Company. All rights reserved.

This microform edition is protected against unauthorized copying under Title 17, United States Code. ProQuest Information and Learning Company 300 North Zeeb Road P. Box 1346 Ann Arbor, MI 48106-1346 Copyright c Jia Mao, 2007 All rights reserved. The dissertation of Jia Mao is approved, and it is accept- able in quality and form for publication on microfilm: Chair University of California, San Diego 2007 iii To my parents iv CONTENTS Signature Page.

v List of Figures. viii List of Tables. x Vita, Publications, and Fields of Study .2 Online and Dynamic Computations .3 Game-theoretic Notions. 4 2 The Majority Problem .2 Optimal Winning Strategies .1 Current best bounds .3 Upper bounds for M A2 and M A∗ .5 Lower bound for M O∗ when existence is not known.

16 3 Expander Graphs to Rescue .2 Expanders and Optimal Oblivious Strategy. 24 4 From Majority to Plurality .1 A Natural Extension of Majority .2 Optimal Winning Strategies .1 Adaptive strategies for the Plurality problem. 33 5 Majority Game with Liars .1 Error-tolerance and Rényi-Ulam’s Liar Game .2 Majority Game with Liars .1 Majority Game with at most t = 1 lie .2 Majority Game with at most t ≥ 2 lies. 52 6 The 2BPS Problem .1 Motivation and Background .2 Simple Greedy Algorithm A .1 The packing graphs .2 Better Approximation Ratio for 2BPS for large weights .1 More about the packing graphs .1 (2 − 1/k)-approximation Algorithm Ak .2 A lower bound for all online algorithms.

73 7 An ε-Improvement Approximation .2 ε-Improvement for 2BPS .3 Better Approximation Ratio for large Weights .1 The IN C k algorithm. 100 9 Summary and Discussion. 102 Appendix A: Proof of Lower Bound of M O2 [67]. 104 Appendix B: Proof of Theorem 6.

109 vii LIST OF FIGURES Figure 2.1: An auxiliary graph on a set of n = 5 elements {a, b, c, d, e} each with a binary label (k = 2). The blue edges denote the “equal” answer for label comparisons and the red edges denote the “unequal” answers. Note that the actual labelling is not revealed to Q until the end of the game.1: “Oblivious” first round queries.2: Looking for lies in the spokes.3: Oblivious graph, n even.4: Oblivious graph, n odd.5: The remaining two-cycles for a side edge e.1: Two valid packings with corresponding graphs for a list of three weights (2/3, 1/2, 1/4) .2: Algorithm A achieves a close-to-optimal approximation ratio as all weights become large.1: A chain of length 4.2: Matching graph of original tiny weights of type B and C and nice large weights, arranged in non-decreasing size on the left side and non-increasing size on the right side. The nice large weights are also grouped according to the chains in IN C(L).

87 viii LIST OF TABLES Table 2.1: Notations for minimum length of Q’s winning strategies for the Majority Game .2: Current Best Bounds for the Majority Game .1: Notations for minimum length of Q’s winning strategies for the Plurality Game .2: Current Best Bounds for the Plurality Game .1: Current Best Bounds for the Majority Game with Liar (up to t lies, binary labels). 36 ix ACKNOWLEDGEMENTS First I thank the Lord for His unfathomable love and grace for me. To Him be all the glory. My sincere gratitude also goes to many friends, colleagues and family members.

Without their support, this dissertation would still be far from complete. Specially, I would like to thank my advisor Ron Graham for his contin- uous encouragement and invaluable guidance throughout my graduate study; my mentors/collaborators Fan Chung, Andrew Chi-Chih Yao and George Varghese for helping me in so many ways; my other collaborator Steven Butler with whom it has been a great pleasure working; my family for being there for me in good times and bad; and Fu Liu for her faithful friendship. Chapter 2 and 4 contain material appearing in “Finding favorites” from Electronic Colloquium on Computational Complexity(ECCC) (078) 2003 and “Obliv- ious and Adaptive Strategies for the Majority and Plurality Problems” from the 11th International Computing and Combinatorics Conference (COCOON) 2005: 329-338, and material to appear in Algorithmica. Chapter 5 contains material sub- mitted for publication.

Chapter 6 and 8 contain material appearing in “Parallelism vs. Memory Allocation in Pipelined Router Forwarding Engines” from Theory of Computing Systems (ToCS), ISSN 1432-4350 (Print) 1433-0490 (Online) 2006. Chapter 6 and 7 contain material submitted for publication. I would like to thank my co-authors Fan Chung, Ron Graham, George Varghese, Andrew Chi-Chih Yao, and Steven Butler.

with Honors, California Institute of Technology 2004 M., University of California, San Diego 2007 Ph., University of California, San Diego RELATED PAPERS and PREPRINTS “Oblivious Strategies in the Majority and Plurality Problems”. Algorithmica, to appear, 2006. “How to Play the Majority Game with Liars”. Discrete Applied Mathematics, under review, 2006.

Memory Allocation in Pipelined Router Forwarding Engines”. Theory of Computing Systems (ToCS), ISSN 1432-4350 (Print) 1433-0490 (Online), 2006. Electronic Collo- quium on Computational Complexity (ECCC)(078), 2003. “Oblivious Strategies in the Majority and Plurality Problems”.

Computing and Combinatorics (COCOON) 2005, pp. “How to Play the Majority Game with Liars”. Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algo- rithms and Applications (CS), oral presentation, 2006. “Parallel Resource Allocation of Splittable Items with Cardinality Constraints”.

FIELDS OF STUDY Computer Science Studies in Algorithms and Complexity Professor Ronald L. Graham xi ABSTRACT OF THE DISSERTATION On the Design and Worst-Case Analysis of Certain Interactive and Approximation Algorithms by Jia Mao Doctor of Philosophy in Computer Science University of California, San Diego, 2007 Professor Ronald L. Graham, Chair With the speed of current technological changes, computation models are evolv- ing 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. In this work we present and study some interactive and dynamic computations and design efficient algorithmic schemes to solve them. Our approach for perfor- mance evaluation falls within the framework of worst-case analysis. The worst-case scenarios are analyzed through the incorporation of imaginary adversaries or adver- sarial input sequences.

Worst-case analysis provides safe performance guarantees even when we have little or no prior knowledge about the input sequences. An- other 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. We first address a particular computation problem of interactive nature, best xii known as the Majority/Plurality game.

This interactive game has appeared in sev- eral different contexts since the 1980s such as system diagnosis and group testing. We design and analyze optimal strategies to minimize the amount of communica- tion needed in different settings against an imaginary adversary. We also consider error-tolerance features to make our strategies robust even in the presence of com- munication errors. We then introduce a new variant of the classical bin packing problem that al- lows 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 nat- ural to other similar resource allocation applications. Even the simplest case of this problem can be shown to be NP-hard. We design efficient approximation al- gorithms in the offline, online, and dynamic settings.

We also use an interesting ε-improvement technique to show improved approximation ratios. xiii 1 Introduction The rapid developments of computing device and network technologies have changed the world around us. One aspect of this change is that traditional com- putation models have evolved to be increasingly distributive and interactive. In- evitably, these new computation models are of great importance and have gained more and more attention in the research community in recent years.

However, our understanding for these models is still quite inadequate and challenging new problems are emerging on a regular basis. It is common to observe that some of these problems are interactive in nature and others face the reality that not every piece of the information needed for decision making is available a priori. Consequently, algorithm design for these problems is in need of new insight and new techniques. In this work we present and study some interactive and dynamic computations and design efficient algorithmic schemes to solve them.

A powerful tool in our analysis is graphical representation which evolves as the computation progresses, naturally adapting to an interactive or dynamic computation environ- ment. Graphs not only help us visualize the computations step by step, but more importantly, offer us powerful mathematical tools from the well-developed area of graph theory. 1 2 To evaluate the performance of the algorithms, a worst-case approach is adopted through the incorporation of imaginary adversaries or adversarial input sequences. This is in contrast to another commonly used approach, average-case analysis, where a distribution of input sequences is hypothesized and the expected total cost or performance is evaluated.

Worst-case analysis attempts to finesse the issue of little or no prior knowledge about what the input sequences are likely by taking a pessimistic approach.1 Interactive Computations A basic theme for interactive computing involves two or more parties and a sequence of queries/answers where each query or answer can depend on previous ones. Here by interactive computing, what we mean is different from the operating system research point of view, where interactive computing usually corresponds to timesharing and refers to the case that a user can communicate and respond to the computer’s responses in a way that batch processing does not allow [62]. Unlike the generic computation models, our understanding for interactive computing is far from adequate. However, with the convergence of communication, computation, and large shared information sources, the need for a solid theoretical foundation for interactive computing is imperative.

In the first part of this dissertation, we focus on a particular type of interactive game, called the Majority/Plurality game. It is an information-theoretic identifi- cation problem that first appeared in the 1980s [51]. We encountered this problem again in a practical context where a good sensor needs to be identified from a set of sensors in which some are non-operational or corrupted and it is desired to minimize the amount of intercommunication used in doing so [64] [23]. There are many interesting variants of the original problem [1].

We will survey related 3 literature, discuss these variants and devise effective strategies to solve them.2 Online and Dynamic Computations Online computations make a sequence of decisions under uncertainty [17]. One of the most powerful methods of analyzing such problems is competitive analysis, which is a type of worst-case analysis. The competitive ratio of an algorithm is the worst-case ratio of its performance to the performance of the best offline algorithm. In the second part of this dissertation, motivated by a practical problem of al- locating memories to parallel processors in the context of designing fast IP lookup schemes [21], we propose a new variant of the classical bin packing problem - kBPS.

This variant can be shown to be NP-hard even in the simplest case. We will design efficient approximation algorithms for this problem in the offline, on- line, and dynamic settings.