A fresh view on $k$-sum optimization and the Discrete Ordered Median Problem: A general framework

In a remarkable paper by Ogryczak and Tamir \cite{OT2003} these authors introduce a novel linear time algorithms to compute the sum of the $q$-largest entries ($q\le n$) of an arbitrary vector of $n$ components. This idea was later exploited by \cite{KNPT2002,Nickel2005} to develop an efficient representation for the $q$-centrum location problem and more generally extended to deal with the Monotone Discrete Ordered Median Problem (DOMP). The extraordinary performance that is obtained by the above formulations in the \textit{convex} cases, leads us to extend the rationale behind the $q$-sum representations to be used in a more general framework where monotonicity of the lambda vector is lost. In this talk, we address continuous, integer and combinatorial $k$-sum optimization  problems. We analyze different formulations of this problem that allow to solve it through the minimization of a relatively small number of minisum optimization problems. This approach provides a general tool for  solving a variety of $k$-sum optimization problems and at the same time, improves the complexity bounds of many  ad-hoc algorithms  previously reported in the literature for particular versions of this problem. Moreover, the results developed for $k$-sum optimization  have been extended to the more general case of the  convex ordered median problem, improving upon existing solution approaches.
This fact can be exploited leading to new formulations for DOMP which in fact is general enough to accommodate not only non-monotonic but also negative lambda values. This talk presents a novel formulation for DOMP valid for general (non-monotonic and positive and negative) lambda based on combining the efficient representations of $q$-sums of costs and the rationale of telescopic sums already applied in previous formulations for DOMP as in \cite{Marin2009}.

Homepage1 of Justo Puerto
Homepage2 of Justo Puerto