Local Approximability of Max-Min and Min-Max Linear Programs |
| |
| Authors: | Patrik Floréen Marja Hassinen Joel Kaasinen Petteri Kaski Topi Musto Jukka Suomela |
| |
| Affiliation: | 1.Helsinki Institute for Information Technology HIIT,University of Helsinki,Helsinki,Finland |
| |
| Abstract: | In a max-min LP, the objective is to maximise ω subject to A
x≤1, C
x≥ω
1, and x≥0. In a min-max LP, the objective is to minimise ρ subject to A
x≤ρ
1, C
x≥1, and x≥0. The matrices A and C are nonnegative and sparse: each row a
i
of A has at most Δ
I
positive elements, and each row c
k
of C has at most Δ
K
positive elements. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
