Revisiting \(k\)-sum optimization

DOI10.1007/s10107-016-1096-1zbMath1373.90068OpenAlexW2561126274MaRDI QIDQ1675256

Arie Tamir, Justo Puerto, Antonio M. Rodríguez-Chía

Publication date: 27 October 2017

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-016-1096-1

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Continuous location (90B85) Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Related Items

Mathematical programming formulations for the efficient solution of the \(k\)-sum approval voting problem, Extensive facility location problems on networks: an updated review, The nestedness property of location problems on the line, Using \(\ell^p\)-norms for fairness in combinatorial optimisation, Portfolio problems with two levels decision-makers: optimal portfolio selection with pricing decisions on transaction costs, Ordered \(p\)-median problems with neighbourhoods, A fresh view on the discrete ordered median problem based on partial monotonicity, Unnamed Item, Bridging \(k\)-sum and CVaR optimization in MILP, New algorithmic framework for conditional value at risk: application to stochastic fixed-charge transportation, The ordered \(k\)-median problem: surrogate models and approximation algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On discrete optimization with ordering
• The \(k\)-centrum Chinese postman delivery problem and a related cost allocation game
• Balanced optimization problems
• An O(n) algorithm for the linear multiple choice knapsack problem and related problems
• Improved complexity results for several multifacility location problems on trees
• k-sum optimization problems
• The \(k\)-centrum shortest path problem
• A strongly polynomial minimum cost circulation algorithm
• Improved complexity bounds for location problems on the real line
• Lexicographic bottleneck problems
• Geometric algorithms and combinatorial optimization
• Fully polynomial approximation schemes for locating a tree-shaped facility: A generalization of the knapsack problem
• An improved general procedure for lexicographic bottleneck problems
• Improved algorithms for several network location problems with equality measures.
• Robust discrete optimization and network flows
• The centdian subtree on tree networks
• Locating tree-shaped facilities using the ordered median objective
• Algorithms for path medi-centers of a tree
• Minimizing the sum of the \(k\) largest functions in linear time.
• Algorithmic results for ordered median problems
• On \(k\)-sum optimization
• Ordered weighted average combinatorial optimization: formulations and their properties
• An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs
• On the p-median polytope of fork-free graphs
• Location Theory
• On locating path- or tree-shaped facilities on networks
• Medi-Centers of a Tree
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Centers to centroids in graphs
• Combinatorial Optimization with Rational Objective Functions
• Thek-nucleus of a graph
• K-Sum Linear Programming
• Finding Minimal Center-Median Convex Combination (Cent-Dian) of a Graph
• A polynomial algorithm for thep-centdian problem on a tree
• Slowing down sorting networks to obtain faster sorting algorithms
• Multifacility ordered median problems on networks: A further analysis
• Finding cores of limited length
• Polynomial algorithms for partitioning a tree into single‐center subtrees to minimize flat service costs
• The \(k\)-centrum multi-facility location problem