Approximation Algorithm for Generalized Budgeted Assignment Problems and Applications in Transportation Systems
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912065344503808 |
|---|---|
| author | Jiang, Hongyi Samaranayake, Samitha |
| author_facet | Jiang, Hongyi Samaranayake, Samitha |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_11832 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Approximation Algorithm for Generalized Budgeted Assignment Problems and Applications in Transportation Systems Jiang, Hongyi Samaranayake, Samitha Optimization and Control 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. |
| title | Approximation Algorithm for Generalized Budgeted Assignment Problems and Applications in Transportation Systems |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2208.11832 |