Approximation Algorithm for Generalized Budgeted Assignment Problems and Applications in Transportation Systems
| Autor: | Jiang, Hongyi, Samaranayake, Samitha |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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 $c_l$ and an $n_l$-dimensional capacity vector. Each item $p$ has an $n_l$-dimensional binary weight vector $r_{lp}$, where the $1$s in $r_{lp}$ (if any) appear in consecutive positions, and its assignment to bin $l$ yields a reward $v_{lp}$. 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. Comment: The preliminary version, titled 'Approximation Algorithms for Capacitated Assignment with Budget Constraints and Applications in Transportation Systems,' was accepted at COCOON 2022. The extended version, now titled 'Approximation Algorithm for Generalized Budgeted Assignment Problems and Applications in Transportation Systems,' was accepted by Discrete Applied Mathematics |
| Databáze: | arXiv |
| Externí odkaz: |
|