Search Results

Documents authored by Wong, Prudence W. H.

Document
DOI: 10.4230/LIPIcs.SAND.2026.13
Online Algorithms for Set Packing with Renewable Capacities

Authors: Anya Chaturvedi, William K. Moses Jr., Christian Scheideler, and Prudence W. H. Wong

Published in: LIPIcs, Volume 373, 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)

Abstract
We propose and study a new extension of the classical set packing problem, which we call the online D-set packing with renewable capacities (D-SPaRC) problem. In the D-SPaRC setting, there is a collection of resources with associated capacities. Requests arrive one by one, and for each request, a decision has to be made to accept it or not before seeing future requests. Each request is associated with a collection of subsets of resources, with each subset having cardinality at most D. When accepting a request, exactly one of these subsets must be chosen, which consumes one unit of capacity on each of the involved resources. Over time, the available resource capacities may be renewed, allowing additional requests to be accepted. Many online problems, including packing, routing, and scheduling, can be formulated as a D-SPaRC problem, thus underlining its usefulness. We first present a simple greedy algorithm that is O(ĉ_min ⋅ (D^{1/ĉ_min}-1))-competitive for D ≥ 2 and 3-competitive if D = 1, where ĉ_min is the minimum capacity of the resources. We then show that, for ĉ_min = Ω(log D), the greedy algorithm can be extended to an online algorithm with predictions whose competitive ratio is never worse than that of the original greedy approach and can, in fact, be reduced to a constant when the predictions are optimal. Finally, we generalize the D-SPaRC problem in two meaningful ways, namely by addressing non-uniform request priorities and by handling requests with non-uniform weights.
Cite as

Anya Chaturvedi, William K. Moses Jr., Christian Scheideler, and Prudence W. H. Wong. Online Algorithms for Set Packing with Renewable Capacities. In 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 373, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chaturvedi_et_al:LIPIcs.SAND.2026.13,
  author =	{Chaturvedi, Anya and Moses Jr., William K. and Scheideler, Christian and Wong, Prudence W. H.},
  title =	{{Online Algorithms for Set Packing with Renewable Capacities}},
  booktitle =	{5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)},
  pages =	{13:1--13:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-427-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{373},
  editor =	{Mertzios, George B. and Richa, Andr\'{e}a W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2026.13},
  URN =		{urn:nbn:de:0030-drops-262472},
  doi =		{10.4230/LIPIcs.SAND.2026.13},
  annote =	{Keywords: Set packing, online algorithms, learning-augmented algorithms}
}
Document
DOI: 10.4230/LIPIcs.SEA.2017.32
The Impact of Landscape Sparsification on Modelling and Analysis of the Invasion Process

Authors: Daniyah A. Aloqalaa, Jenny A. Hodgson, and Prudence W. H. Wong

Published in: LIPIcs, Volume 75, 16th International Symposium on Experimental Algorithms (SEA 2017)

Abstract
Climate change is a major threat to species, unless their populations are able to invade and colonise new landscapes of more suitable environment. In this paper, we propose a new model of the invasion process using a tool of landscape network sparsification to efficiently estimate a duration of the process. More specifically, we aim to simplify the structure of large landscapes using the concept of sparsification in order to substantially decrease the time required to compute a good estimate of the invasion time in these landscapes. For this purpose, two different simulation methods have been compared: full and R-local simulations, which are based on the concept of dense and sparse networks, respectively. These two methods are applied to real heterogeneous landscapes in the United Kingdom to compute the total estimated time to invade landscapes. We examine how the duration of the invasion process is affected by different factors, such as dispersal coefficient, landscape quality and landscape size. Extensive evaluations have been carried out, showing that the R-local method approximates the duration of the invasion process to high accuracy using a substantially reduced computation time.
Cite as

Daniyah A. Aloqalaa, Jenny A. Hodgson, and Prudence W. H. Wong. The Impact of Landscape Sparsification on Modelling and Analysis of the Invasion Process. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 32:1-32:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{aloqalaa_et_al:LIPIcs.SEA.2017.32,
  author =	{Aloqalaa, Daniyah A. and Hodgson, Jenny A. and Wong, Prudence W. H.},
  title =	{{The Impact of Landscape Sparsification on Modelling and Analysis of the Invasion Process}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{32:1--32:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.32},
  URN =		{urn:nbn:de:0030-drops-76160},
  doi =		{10.4230/LIPIcs.SEA.2017.32},
  annote =	{Keywords: Landscape sparsification, invasion process, network sparsification, dense and sparse networks}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.53
Optimal Nonpreemptive Scheduling in a Smart Grid Model

Authors: Fu-Hong Liu, Hsiang-Hsuan Liu, and Prudence W. H. Wong

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
We study a scheduling problem arising in demand response management in smart grid. Consumers send in power requests with a flexible feasible time interval during which their requests can be served. The grid controller, upon receiving power requests, schedules each request within the specified interval. The electricity cost is measured by a convex function of the load in each timeslot. The objective is to schedule all requests with the minimum total electricity cost. Previous work has studied cases where jobs have unit power requirement and unit duration. We extend the study to arbitrary power requirement and duration, which has been shown to be NP-hard. We give the first online algorithm for the general problem, and prove that the worst case competitive ratio is asymptotically optimal. We also prove that the problem is fixed parameter tractable. Due to space limit, the missing proofs are presented in the full paper.
Cite as

Fu-Hong Liu, Hsiang-Hsuan Liu, and Prudence W. H. Wong. Optimal Nonpreemptive Scheduling in a Smart Grid Model. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 53:1-53:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.ISAAC.2016.53,
  author =	{Liu, Fu-Hong and Liu, Hsiang-Hsuan and Wong, Prudence W. H.},
  title =	{{Optimal Nonpreemptive Scheduling in a Smart Grid Model}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{53:1--53:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.53},
  URN =		{urn:nbn:de:0030-drops-68252},
  doi =		{10.4230/LIPIcs.ISAAC.2016.53},
  annote =	{Keywords: Scheduling, Smart Grid, Convex function cost, Fixed parameter tractable, Online algorithms, Non-preemptive}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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