๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Minimizing the sum of the k largest functions in linear time

โœ Scribed by Wlodzimierz Ogryczak; Arie Tamir

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
93 KB
Volume
85
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis

Given a collection of n functions defined on R d , and a polyhedral set Q โŠ‚ 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 Tamir [

๐Ÿ“œ SIMILAR VOLUMES

On minimizing the sum of k tardiness
On minimizing the sum of k tardiness
โœ Gerhard Woeginger ๐Ÿ“‚ Article ๐Ÿ“… 1991 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 482 KB
On the sum of k largest singular values
On the sum of k largest singular values of graphs and matrices
โœ Vladimir Nikiforov ๐Ÿ“‚ Article ๐Ÿ“… 2011 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 164 KB

In the recent years, the trace norm of graphs has been extensively studied under the name of graph energy. The trace norm is just one of the Ky Fan k-norms, given by the sum of the k largest singular values, which are studied more generally in the present paper. Several relations to chromatic number