Can I read Approximation Algorithm for Generalized Budgeted Assignment Problems and Applications in Transportation Systems on EtoBox?

Approximation Algorithm for Generalized Budgeted Assignment Problems and Applications in Transportation Systems by Jiang, Hongyi; Samaranayake, Samitha is a scholarly article available to read on EtoBox.

What is Approximation Algorithm for Generalized Budgeted Assignment Problems and Applications in Transportation Systems about?

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.

Author

Jiang, Hongyi; Samaranayake, Samitha

Published

2022

Language

EN