Minimizing the sum of the \(k\) largest functions in linear time.
type: Item
instance of: scholarly article
title: Minimizing the sum of the \(k\) largest functions in linear time.
zbMATH Open document ID: 1050.68155
DOI: 10.1016/S0020-0190(02)00370-8
author: W. Ogryczak
author: Arie Tamir
published in: Information Processing Letters
publication date: 2003-01-22T00:00:00Z
review text: 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)].
Mathematics Subject Classification ID: 68U05
Mathematics Subject Classification ID: 90B85
zbMATH DE Number: 1857179
zbMATH Keywords: Algorithms
zbMATH Keywords: Computational geometry
zbMATH Keywords: Location
zbMATH Keywords: Rectilinear
MaRDI profile type: Publication
cites work: k-Eccentricity and absolute k-centrum of a probabilistic tree
cites work: Properties of thek-centra in a tree network
cites work: Maximizing concave functions in fixed dimension
cites work: Aggregation Error Bounds for a Class of Location Models
cites work: Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph
cites work: Optimum Distribution of Switching Centers in a Communication Network and Some Related Graph Theoretic Problems
cites work: Finding Minimal Center-Median Convex Combination (Cent-Dian) of a Graph
cites work: Duality in the Cent-Dian of a Graph
cites work: Medi-Centers of a Tree
cites work: Algorithmic results for ordered median problems
cites work: Linear Programming in Linear Time When the Dimension Is Fixed
cites work: Linear time algorithms for some separable quadratic programming problems
cites work: Q4934873
cites work: Inequality measures and equitable approaches to location problems
cites work: Geometrical properties of the symmetrical single facility location problem
cites work: Centers to centroids in graphs
cites work: The \(k\)-centrum multi-facility location problem
cites work: A polynomial algorithm for thep-centdian problem on a tree
cites work: A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
cites work: Minimax parametric optimization problems and multi-dimensional parametric searching
cites work: On ordered weighted averaging aggregation operators in multicriteria decisionmaking
cites work: An O(n) algorithm for the linear multiple choice knapsack problem and related problems
full work available at URL: s0020-0190(02)00370-8
OpenAlex ID: W2150338193
Recommended article: A Linear Time Algorithm for the k Maximal Sums Problem
Recommended article: Efficient algorithms for \(k\) maximum sums
Recommended article: Algorithms and Computation
Recommended article: Solving k-SUM using few linear queries
Recommended article: Minimizing a sum of submodular functions
Recommended article: Efficient Algorithms for the Sum Selection Problem and K Maximum Sums Problem
Recommended article: Efficient algorithms for the sum selection problem and \(k\) maximum sums problem
Recommended article: Towards Minimizing k-Submodular Functions
Recommended article: A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
Recommended article: On \(k\)-sum optimization
description: scientific article; zbMATH DE number 1857179