Author name cluster

Tak-Wah Lam

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers

1 author row

TCS Journal 2013 Journal Article

Scheduling for weighted flow time and energy with rejection penalty

Sze-Hang Chan
Tak-Wah Lam
Lap-Kei Lee

This paper revisits the online problem of flow-time scheduling on a single processor when jobs can be rejected at some penalty (Bansal et al. 2003) [4]. The user cost of a job is defined as the weighted flow time of the job plus the penalty if it is rejected before completion. For jobs with arbitrary weights and arbitrary penalties, Bansal et al. (2003) [4] gave an online algorithm that is O ( ( log W + log C ) 2 ) -competitive for minimizing the total user cost when using a slightly faster processor, where W and C are the max–min ratios of job weights and job penalties, respectively. In this paper we improve this result with a new algorithm that can achieve a constant competitive ratio independent of W and C when using a slightly faster processor. Note that the above results assume a processor running at a fixed speed. This paper shows more interesting results on extending the above study to the dynamic speed scaling model and adding energy into consideration, where the processor can vary the speed dynamically and the rate of energy consumption is a cubic or any increasing function of speed. A scheduling algorithm has to control job admission and determine the order and speed of job execution. This paper studies the tradeoff between the above-mentioned user cost and energy, and it shows two O ( 1 ) -competitive algorithms and a lower bound result on minimizing the user cost plus energy. These algorithms can also be regarded as a generalization of the recent work on minimizing flow time plus energy when all jobs must be completed (see the survey paper Albers (2010) [1]).

Details DOI

TCS Journal 2011 Journal Article

Cache-oblivious index for approximate string matching

Wing-Kai Hon
Tak-Wah Lam
Rahul Shah
Siu-Lung Tam
Jeffrey Scott Vitter

This paper revisits the problem of indexing a text for approximate string matching. Specifically, given a text T of length n and a positive integer k, we want to construct an index of T such that for any input pattern P, we can find all its k -error matches in T efficiently. This problem is well-studied in the internal-memory setting. Here, we extend some of these recent results to external-memory solutions, which are also cache-oblivious. Our first index occupies O ( ( n log k n ) / B ) disk pages and finds all k -error matches with O ( ( | P | + o c c ) / B + log k n log log B n ) I/Os, where B denotes the number of words in a disk page. To the best of our knowledge, this index is the first external-memory data structure that does not require Ω ( | P | + o c c + poly ( log n ) ) I/Os. The second index reduces the space to O ( ( n log n ) / B ) disk pages, and the I/O complexity is O ( ( | P | + o c c ) / B + log k ( k + 1 ) n log log n ).

Details DOI

TCS Journal 2010 Journal Article

Deadline scheduling and power management for speed bounded processors

Xin Han
Tak-Wah Lam
Lap-Kei Lee
Isaac K.K. To
Prudence W.H. Wong

In this paper we consider online deadline scheduling on a processor that can manage its energy usage by scaling the speed dynamically or entering a sleep state. A new online scheduling algorithm called SOA is presented. Assuming speed can be scaled arbitrarily high (the infinite speed model), SOA can complete all jobs with reduced energy usage, improving the competitive ratio for energy from 2 2 α − 2 α α + 2 α − 1 + 2 (Irani et al. (2007) [17]) to α α + 2, where α is the constant involved in the speed-to-power function, commonly believed to be 2 or 3. More importantly, SOA is the first algorithm that works well even if the processor has a fixed maximum speed and the system is overloaded. In this case, SOA is 4-competitive for throughput and ( α α + α 2 4 α + 2 ) -competitive for energy. Note that the throughput ratio cannot be better than 4 even if energy is not a concern.

Details DOI

TCS Journal 2008 Journal Article

Dynamic bin packing of unit fractions items

Joseph Wun-Tat Chan
Tak-Wah Lam
Prudence W.H. Wong

This paper studies the dynamic bin packing problem, in which items arrive and depart at arbitrary times. We want to pack a sequence of unit fractions items (i. e. , items with sizes 1 / w for some integer w ≥ 1 ) into unit-size bins, such that the maximum number of bins ever used over all time is minimized. Tight and almost-tight performance bounds are found for the family of any-fit algorithms, including first-fit, best-fit, and worst-fit. In particular, we show that the competitive ratio of best-fit and worst-fit is 3, which is tight, and the competitive ratio of first-fit lies between 2. 45 and 2. 4942. We also show that no on-line algorithm is better than 2. 428-competitive.

Details DOI

TCS Journal 2006 Journal Article

Approximate string matching using compressed suffix arrays

Trinh N.D. Huynh
Wing-Kai Hon
Tak-Wah Lam
Wing-Kin Sung

Let T be a text of length n and P be a pattern of length m, both strings over a fixed finite alphabet A. The k -difference ( k -mismatch, respectively) problem is to find all occurrences of P in T that have edit distance (Hamming distance, respectively) at most k from P. In this paper we investigate a well-studied case in which T is fixed and preprocessed into an indexing data structure so that any pattern query can be answered faster. We give a solution using an O ( n log n ) bits indexing data structure with O ( | A | k m k · max ( k, log n ) + occ ) query time, where occ is the number of occurrences. The best previous result requires O ( n log n ) bits indexing data structure and gives O ( | A | k m k + 2 + occ ) query time. Our solution also allows us to exploit compressed suffix arrays to reduce the indexing space to O ( n ) bits, while increasing the query time by an O ( log n ) factor only.

Details DOI

TCS Journal 2006 Journal Article

New resource augmentation analysis of the total stretch of SRPT and SJF in multiprocessor scheduling

Wun-Tat Chan
Tak-Wah Lam
Kin-Shing Liu
Prudence W.H. Wong

This paper studies online job scheduling on multiprocessors and, in particular, investigates the algorithms Shortest Remaining Processing Time First (SRPT) and Shortest Job First (SJF) for minimizing total stretch, where the stretch of a job is its flow time (response time) divided by its processing time. SRPT is perhaps the most well-studied algorithm for minimizing total flow time or stretch. This paper gives the first resource augmentation analysis of the total stretch of SRPT, showing that it is indeed O ( 1 ) -speed 1-competitive. This paper also gives a simple lower bound result showing that SRPT is not s-speed 1-competitive for any s < 1. 5. This paper also makes contribution to the analysis of SJF. Extending the work of [L. Becchetti, S. Leonardi, A. Marchetti-Spaccamela, K. Pruhs, Online weighted flow time and deadline scheduling, in: RANDOM-APPROX, 2001, pp. 36–47], we are able to show that SJF is O ( 1 ) -speed 1-competitive for minimizing total stretch. More interestingly, we find that the competitiveness of SJF can be reduced arbitrarily by increasing the processor speed (precisely, SJF is O ( s ) -speed ( 1 / s ) -competitive for any s ⩾ 1 ). We conjecture that SRPT also admits a similar result.

Details DOI

TCS Journal 2003 Journal Article

On-line scheduling with tight deadlines

Chiu-Yuen Koo
Tak-Wah Lam
Tsuen-Wan Ngan
Kunihiko Sadakane
Kar-Keung To

This paper is concerned with the on-line problem of scheduling jobs with tight deadlines in a uni-processor system. It has been known for long that in such a setting, no on-line algorithm is 1-competitive (i. e. , optimal) in the sense of matching the optimal off-line algorithm on the total value of jobs that meet the deadlines; indeed, no algorithm can be better than k-competitive, where k is the importance ratio of the jobs. Recent work, however, reveals that the competitive ratio can be improved to a constant if the on-line scheduler is equipped with a processor O(1) times faster (J. ACM 47(4) (2000) 617), and further to one when using a processor O(logk) times faster (Proc. 12th Ann. ACM–SIAM Symp. on Discrete Algorithms, 2001, p. 755). This paper presents a new on-line algorithm for scheduling jobs with tight deadlines and shows that it is 1-competitive when using a processor that is only O(1) times faster.

Details DOI

TCS Journal 2003 Journal Article

On-line stream merging in a general setting

Wun-Tat Chan
Tak-Wah Lam
Hing-Fung Ting
Prudence W.H. Wong

This paper is concerned with on-line scheduling algorithms for merging streams in a video-on-demand system so as to minimize the server bandwidth. We present the first algorithm that has a constant competitive factor (precisely, 5). Our algorithm, unlike previous ones, is not limited to the scenario where clients are equipped with large buffer and client receiving bandwidth. It remains 5-competitive in all settings of buffer size and receiving bandwidth. Technically speaking, our algorithm is based on a novel observation that the behavior of any schedule can be modeled by a rectilinear (binary) tree on a grid. This observation eases the analysis of our algorithm as well as the optimal algorithm.

Details DOI

TCS Journal 2002 Journal Article

On-line load balancing of temporary tasks revisited

Tak-Wah Lam
Hing-Fung Ting
Kar-Keung To
Wai-Ha Wong

We study load balancing problems of temporary jobs (i. e. , jobs that arrive and depart at unpredictable time) in two different contexts, namely, machines and network paths. Such problems are known as machine load balancing and virtual circuit routing in the literature. We present new on-line algorithms and improved lower bounds.

Details DOI