Minimizing the sum of the \(k\) largest functions in linear time. (Q1853685)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Minimizing the sum of the \(k\) largest functions in linear time.
scientific article

    Statements

    Minimizing the sum of the \(k\) largest functions in linear time. (English)
    0 references
    0 references
    0 references
    22 January 2003
    0 references
    Given a collection of \(n\) functions defined on \(R^{d},\) and a polyhedral set \(Q\subset R^{d}\), we consider the problem of minimizing the sum of the \(k\) largest functions of the collection over \(Q.\) Specifically we focus on collections of linear functions and several classes of convex, piecewise linear functions which are defined by location models. We present simple linear programming formulations for these optimization models which give rise to linear-time algorithms when the dimension \(d\) is fixed. Our results improve complexity bounds of several problems reported recently by \textit{A. Tamir} [Discrete Appl. Math. 109, 293--307 (2001; Zbl 0986.90018)], \textit{Tokuyama} [Proc. 33rd Annual ACM Symp. on Theory of Computing, 75--84 (2001)] and \textit{J. Kalcsics, S. Nickel, J. Puerto} and \textit{A. Tamir} [Oper. Res. Lett. 30, 149--158 (2002; Zbl 1010.90036)].
    0 references
    0 references
    Algorithms
    0 references
    Computational geometry
    0 references
    Location
    0 references
    Rectilinear
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references