Local Approximability of Max-Min and Min-Max Linear Programs

被引：0
|
作者：
Patrik Floréen
Marja Hassinen
Joel Kaasinen
Petteri Kaski
Topi Musto
Jukka Suomela
机构：
[1] University of Helsinki,Helsinki Institute for Information Technology HIIT
来源：
Theory of Computing Systems | 2011年 / 49卷
关键词：
Approximation algorithms; Distributed algorithms; Linear programs; Local algorithms;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
In a max-min LP, the objective is to maximise ω subject to Ax≤1, Cx≥ω1, and x≥0. In a min-max LP, the objective is to minimise ρ subject to Ax≤ρ1, Cx≥1, and x≥0. The matrices A and C are nonnegative and sparse: each row ai of A has at most ΔI positive elements, and each row ck of C has at most ΔK positive elements.
引用
收藏
页码：672 / 697
页数：25
相关论文
共 50 条
  • [1] Local Approximability of Max-Min and Min-Max Linear Programs
    Floreen, Patrik
    Hassinen, Marja
    Kaasinen, Joel
    Kaski, Petteri
    Musto, Topi
    Suomela, Jukka
    THEORY OF COMPUTING SYSTEMS, 2011, 49 (04) : 672 - 697
  • [2] Min-max and max-min graph saturation parameters
    Sudha, S.
    Arumugam, S.
    AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2020, 17 (03) : 943 - 947
  • [3] A Deterministic Algorithm for Min-max and Max-min Linear Fractional Programming Problems
    Qigao Feng
    Hongwei Jiao
    Hanping Mao
    Yongqiang Chen
    International Journal of Computational Intelligence Systems, 2011, 4 (2) : 134 - 141
  • [4] A Deterministic Algorithm for Min-max and Max-min Linear Fractional Programming Problems
    Feng, Qigao
    Jiao, Hongwei
    Mao, Hanping
    Chen, Yongqiang
    INTERNATIONAL JOURNAL OF COMPUTATIONAL INTELLIGENCE SYSTEMS, 2011, 4 (02): : 134 - 141
  • [5] Max-max, max-min, min-max and min-min knapsack problems with a parametric constraint
    Halman, Nir
    Kovalyov, Mikhail Y.
    Quilliot, Alain
    4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2023, 21 (02): : 235 - 246
  • [6] Approximating max-min linear programs with local algorithms
    Floreen, Patrik
    Kaski, Petteri
    Musto, Topi
    Suomela, Jukka
    2008 IEEE INTERNATIONAL SYMPOSIUM ON PARALLEL & DISTRIBUTED PROCESSING, VOLS 1-8, 2008, : 996 - 1005
  • [7] Gumbel central limit theorem for max-min and min-max
    Eliazar, Iddo
    Metzler, Ralf
    Reuveni, Shlomi
    PHYSICAL REVIEW E, 2019, 100 (02)
  • [8] A unified framework for max-min and min-max fairness with applications
    Radunovic, Bozidar
    Le Boudec, Jean-Yves
    IEEE-ACM TRANSACTIONS ON NETWORKING, 2007, 15 (05) : 1073 - 1083
  • [9] Tight Local Approximation Results for Max-Min Linear Programs
    Floreen, Patrik
    Hassinen, Marja
    Kaski, Petteri
    Suomela, Jukka
    ALGORITHMIC ASPECTS OF WIRELESS SENSOR NETWORKS, 2008, 5389 : 2 - +
  • [10] An Optimal Local Approximation Algorithm for Max-Min Linear Programs
    Floreen, Patrik
    Kaasinen, Joel
    Kaski, Petteri
    Suomela, Jukka
    SPAA'09: PROCEEDINGS OF THE TWENTY-FIRST ANNUAL SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES, 2009, : 260 - 269
12345