Balanced optimization with vector costs

Annette Ficker, Frits Spieksma and Gerhard Woeginger

No 522409, Working Papers of Department of Decision Sciences and Information Management, Leuven from KU Leuven, Faculty of Economics and Business (FEB), Department of Decision Sciences and Information Management, Leuven

Abstract: We consider so-called balanced optimization problems with vector costs. We propose a framework containing such problems; this framework allows us to investigate the complexity and approximability of these problems in a general setting. More concrete, each problem in the framework admits a 2-approximation, and for many problems within the framework this result is best-possible, in the sense that having a polynomial-time algorithm with a performance ratio better than 2 would imply P=NP. Special attention is paid to the balanced assignment problem with vector costs: we show that the problem remains NP-hard even in case of sum costs.

Keywords: Balanced optimization; Computational complexity; Approximation; Assignment problem (search for similar items in EconPapers)
Date: 2016-01
References: Add references at CitEc
Citations:

Published in FEB Research Report KBI_1601

Downloads: (external link)
https://lirias.kuleuven.be/bitstream/123456789/522409/1/KBI_1601.pdf Balanced optimization with vector costs (application/pdf)
intranet

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ete:kbiper:522409

Access Statistics for this paper

More papers in Working Papers of Department of Decision Sciences and Information Management, Leuven from KU Leuven, Faculty of Economics and Business (FEB), Department of Decision Sciences and Information Management, Leuven
Bibliographic data for series maintained by library EBIB ().