Approximation algorithm for generalized budgeted assignment problems and applications in transportation systems
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
Original language | English |
---|---|
Pages (from-to) | 383-399 |
Journal / Publication | Discrete Applied Mathematics |
Volume | 359 |
Online published | 2 Oct 2024 |
Publication status | Published - 31 Dec 2024 |
Link(s)
Abstract
Motivated by a transit line planning problem in transportation systems, we investigate the following capacitated assignment problem under a budget constraint. Our model involves L bins and P items. Each bin l has a utilization cost cl and an nl-dimensional capacity vector. Each item p has an nl-dimensional binary weight vector rlp, where the 1s in rlp (if any) appear in consecutive positions, and its assignment to bin l yields a reward vlp. The objective is to maximize total rewards through an assignment that satisfies three constraints: (i) the total weights of assigned items do not violate any bin's capacity; (ii) each item is assigned to at most one open bin; and (iii) the overall utilization costs remain within a total budget B.
We propose the first randomized rounding algorithm with a constant approximation ratio for this problem. We then apply our framework to the motivating transit line planning problem, presenting corresponding models and conducting numerical experiments using real-world data. Our results demonstrate significant improvements over previous approaches in addressing this critical transportation challenge.
© 2024 Elsevier B.V.
We propose the first randomized rounding algorithm with a constant approximation ratio for this problem. We then apply our framework to the motivating transit line planning problem, presenting corresponding models and conducting numerical experiments using real-world data. Our results demonstrate significant improvements over previous approaches in addressing this critical transportation challenge.
© 2024 Elsevier B.V.
Research Area(s)
- Approximation algorithm, Assignment problem, Transportation systems
Citation Format(s)
Approximation algorithm for generalized budgeted assignment problems and applications in transportation systems. / Jiang, Hongyi; Samaranayake, Samitha.
In: Discrete Applied Mathematics, Vol. 359, 31.12.2024, p. 383-399.
In: Discrete Applied Mathematics, Vol. 359, 31.12.2024, p. 383-399.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review