Balanced optimization with vector costs

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

Samenvatting

An instance of a balanced optimization problem with vector costs consists of a ground set X, a vector cost for every element of X, and a system of feasible subsets over X. The goal is to find a feasible subset that minimizes the spread (or imbalance) of values in every coordinate of the underlying vector costs. We investigate the complexity and approximability of balanced optimization problems in a fairly general setting. We identify a large family of problems that admit a 2-approximation in polynomial time, and we show that for many problems in this family this approximation factor 2 is best-possible (unless P=NP). Special attention is paid to the balanced assignment problem with vector costs, which is shown to be NP-hard even in the highly restricted case of sum costs.

Originele taal-2Engels
TitelApproximation and Online Algorithms : 14th International Workshop, WAOA 2016, Revised Selected Papers
RedacteurenK. Jansen, M. Mastrolilli
Plaats van productieCham
UitgeverijSpringer
Pagina's92-102
Aantal pagina's11
ISBN van elektronische versie978-3-319-51741-4
ISBN van geprinte versie978-3-319-51740-7
DOI's
StatusGepubliceerd - 2017
Evenement14th International Workshop on Approximation and Online Algorithms (WAOA 2016) - Lakeside Lecture Theatres ("Søauditorierne") at Aarhus University, Aarhus, Denemarken
Duur: 25 aug 201626 aug 2016
Congresnummer: 14
http://conferences.au.dk/algo16/waoa/
http://conferences.au.dk/algo16/travel-and-local-information/

Publicatie series

NaamLecture Notes in Computer Science
Volume10138
ISSN van geprinte versie0302-9743
ISSN van elektronische versie1611-3349

Congres

Congres14th International Workshop on Approximation and Online Algorithms (WAOA 2016)
Verkorte titelWOA 2016
LandDenemarken
StadAarhus
Periode25/08/1626/08/16
Internet adres

Vingerafdruk Duik in de onderzoeksthema's van 'Balanced optimization with vector costs'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Ficker, A. M. C., Spieksma, F. C. R., & Woeginger, G. J. (2017). Balanced optimization with vector costs. In K. Jansen, & M. Mastrolilli (editors), Approximation and Online Algorithms : 14th International Workshop, WAOA 2016, Revised Selected Papers (blz. 92-102). (Lecture Notes in Computer Science ; Vol. 10138). Springer. https://doi.org/10.1007/978-3-319-51741-4_8