Montag, 21. November 2016, 16:45 - 17:45 iCal
ISOR Colloquium
"A fresh view on $k$-sum optimization and the Discrete Ordered Median Problem: A general framework"
Speaker: Justo Puerto (Univ. Sevilla)
Lecture Hall 12 OMP1 (2nd Floor)
Oskar-Morgenstern-Platz 1, 1090 Vienna
Vortrag
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}.
Zur Webseite der Veranstaltung
Veranstalter
Institut für Statistik und Operations Research
Kontakt
Mag. Vera Lehmwald
Fakultät für Wirtschaftswissenschaften
Institut für Statistik und Operations Research
+43 1 4277 38651
vera.lehmwald@univie.ac.at
Erstellt am Montag, 24. Oktober 2016, 15:32
Letzte Änderung am Dienstag, 25. Oktober 2016, 09:02