Approximation algorithm for generalized budgeted assignment problems and applications in transportation systems

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)383-399
Journal / PublicationDiscrete Applied Mathematics
Volume359
Online published2 Oct 2024
Publication statusPublished - 31 Dec 2024

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.

Research Area(s)

  • Approximation algorithm, Assignment problem, Transportation systems