Search Results

Documents authored by Lee, Lap-Kei

Document
DOI: 10.4230/LIPIcs.STACS.2011.392
Scheduling for Weighted Flow Time and Energy with Rejection Penalty

Authors: Sze-Hang Chan, Tak-Wah Lam, and Lap-Kei Lee

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
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]. 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] 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, 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]).
Cite as

Sze-Hang Chan, Tak-Wah Lam, and Lap-Kei Lee. Scheduling for Weighted Flow Time and Energy with Rejection Penalty. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 392-403, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.STACS.2011.392,
  author =	{Chan, Sze-Hang and Lam, Tak-Wah and Lee, Lap-Kei},
  title =	{{Scheduling for Weighted Flow Time and Energy with Rejection Penalty}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{392--403},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.392},
  URN =		{urn:nbn:de:0030-drops-30293},
  doi =		{10.4230/LIPIcs.STACS.2011.392},
  annote =	{Keywords: online scheduling, weighted flow time, rejection penalty, speed scaling}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2453
Continuous Monitoring of Distributed Data Streams over a Time-based Sliding Window

Authors: Ho-Leung Chan, Tak-Wah Lam, Lap-Kei Lee, and Hing-Fung Ting

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
The past decade has witnessed many interesting algorithms for maintaining statistics over a data stream. This paper initiates a theoretical study of algorithms for monitoring distributed data streams over a time-based sliding window (which contains a variable number of items and possibly out-of-order items). The concern is how to minimize the communication between individual streams and the root, while allowing the root, at any time, to be able to report the global statistics of all streams within a given error bound. This paper presents communication-efficient algorithms for three classical statistics, namely, basic counting, frequent items and quantiles. The worst-case communication cost over a window is $O(\frac{k}{\varepsilon} \log \frac{\varepsilon N}{k})$ bits for basic counting and $O(\frac{k}{\varepsilon} \log \frac{N}{k})$ words for the remainings, where $k$ is the number of distributed data streams, $N$ is the total number of items in the streams that arrive or expire in the window, and $\varepsilon < 1$ is the desired error bound. Matching and nearly matching lower bounds are also obtained.
Cite as

Ho-Leung Chan, Tak-Wah Lam, Lap-Kei Lee, and Hing-Fung Ting. Continuous Monitoring of Distributed Data Streams over a Time-based Sliding Window. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 179-190, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.STACS.2010.2453,
  author =	{Chan, Ho-Leung and Lam, Tak-Wah and Lee, Lap-Kei and Ting, Hing-Fung},
  title =	{{Continuous Monitoring of Distributed Data Streams over a Time-based Sliding Window}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{179--190},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2453},
  URN =		{urn:nbn:de:0030-drops-24536},
  doi =		{10.4230/LIPIcs.STACS.2010.2453},
  annote =	{Keywords: Algorithms, distributed data streams, communication efficiency, frequent items}
}
Document
DOI: 10.4230/LIPIcs.STACS.2009.1815
Nonclairvoyant Speed Scaling for Flow and Energy

Authors: Ho-Leung Chan, Jeff Edmonds, Tak-Wah Lam, Lap-Kei Lee, Alberto Marchetti-Spaccamela, and Kirk Pruhs

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract
We study online nonclairvoyant speed scaling to minimize total flow time plus energy. We first consider the traditional model where the power function is $P(s)=s^\alpha$. We give a nonclairvoyant algorithm that is shown to be $O(\alpha^3)$-competitive. We then show an $\Omega( \alpha^{1/3-\epsilon} )$ lower bound on the competitive ratio of any nonclairvoyant algorithm. We also show that there are power functions for which no nonclairvoyant algorithm can be $O(1)$-competitive.
Cite as

Ho-Leung Chan, Jeff Edmonds, Tak-Wah Lam, Lap-Kei Lee, Alberto Marchetti-Spaccamela, and Kirk Pruhs. Nonclairvoyant Speed Scaling for Flow and Energy. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 255-264, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.STACS.2009.1815,
  author =	{Chan, Ho-Leung and Edmonds, Jeff and Lam, Tak-Wah and Lee, Lap-Kei and Marchetti-Spaccamela, Alberto and Pruhs, Kirk},
  title =	{{Nonclairvoyant Speed Scaling for Flow and Energy}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{255--264},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1815},
  URN =		{urn:nbn:de:0030-drops-18151},
  doi =		{10.4230/LIPIcs.STACS.2009.1815},
  annote =	{Keywords: }
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact