Balanced optimization with vector costs

A.M.C. Ficker; F.C.R. Spieksma; G.J. Woeginger

doi:10.1007/978-3-319-51741-4_8

Balanced optimization with vector costs

A.M.C. Ficker, F.C.R. Spieksma, G.J. Woeginger

Discrete Mathematics

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

1 Citaat (Scopus)

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-2	Engels
Titel	Approximation and Online Algorithms : 14th International Workshop, WAOA 2016, Revised Selected Papers
Redacteuren	K. Jansen, M. Mastrolilli
Plaats van productie	Cham
Uitgeverij	Springer
Pagina's	92-102
Aantal pagina's	11
ISBN van elektronische versie	978-3-319-51741-4
ISBN van geprinte versie	978-3-319-51740-7
DOI's	https://doi.org/10.1007/978-3-319-51741-4_8
Status	Gepubliceerd - 2017
Evenement	14th International Workshop on Approximation and Online Algorithms (WAOA 2016) - Lakeside Lecture Theatres ("Søauditorierne") at Aarhus University, Aarhus, Denemarken Duur: 25 aug. 2016 → 26 aug. 2016 Congresnummer: 14 http://conferences.au.dk/algo16/waoa/ http://conferences.au.dk/algo16/travel-and-local-information/

Publicatie series

Naam	Lecture Notes in Computer Science
Volume	10138
ISSN van geprinte versie	0302-9743
ISSN van elektronische versie	1611-3349

Congres

Congres	14th International Workshop on Approximation and Online Algorithms (WAOA 2016)
Verkorte titel	WOA 2016
Land/Regio	Denemarken
Stad	Aarhus
Periode	25/08/16 → 26/08/16
Internet adres	http://conferences.au.dk/algo16/waoa/ http://conferences.au.dk/algo16/travel-and-local-information/

Financiering

This research has been supported by the Netherlands Organisation for Scientific Research (NWO) under Grant 639.033.403, by BSIK Grant 03018 (BRICKS: Basic Research in Informatics for Creating the Knowledge Society), and by the Interuniversity Attraction Poles Programme initiated by the Belgian Science Policy Office.

Toegang tot document

10.1007/978-3-319-51741-4_8

Andere bestanden en links

Link to publication in Scopus

Citeer dit

@inproceedings{a61501d08f3b4b15a75b2192131e3457,

title = "Balanced optimization with vector costs",

abstract = "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.",

keywords = "Approximation, Assignment problem, Balanced optimization, Computational complexity",

author = "A.M.C. Ficker and F.C.R. Spieksma and G.J. Woeginger",

year = "2017",

doi = "10.1007/978-3-319-51741-4_8",

language = "English",

isbn = "978-3-319-51740-7",

series = "Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "92--102",

editor = "K. Jansen and Mastrolilli, {M. }",

booktitle = "Approximation and Online Algorithms : 14th International Workshop, WAOA 2016, Revised Selected Papers",

address = "Germany",

note = "14th International Workshop on Approximation and Online Algorithms (WAOA 2016), WOA 2016 ; Conference date: 25-08-2016 Through 26-08-2016",

url = "http://conferences.au.dk/algo16/waoa/, http://conferences.au.dk/algo16/travel-and-local-information/",

}

Ficker, AMC, Spieksma, FCR & Woeginger, GJ 2017, Balanced optimization with vector costs. in K Jansen & M Mastrolilli (uitgave), Approximation and Online Algorithms : 14th International Workshop, WAOA 2016, Revised Selected Papers. Lecture Notes in Computer Science , vol. 10138, Springer, Cham, blz. 92-102, 14th International Workshop on Approximation and Online Algorithms (WAOA 2016), Aarhus, Denemarken, 25/08/16. https://doi.org/10.1007/978-3-319-51741-4_8

Balanced optimization with vector costs. / Ficker, A.M.C.; Spieksma, F.C.R.; Woeginger, G.J.
Approximation and Online Algorithms : 14th International Workshop, WAOA 2016, Revised Selected Papers. uitgave / K. Jansen; M. Mastrolilli. Cham: Springer, 2017. blz. 92-102 (Lecture Notes in Computer Science ; Vol. 10138).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

TY - GEN

T1 - Balanced optimization with vector costs

AU - Ficker, A.M.C.

AU - Spieksma, F.C.R.

AU - Woeginger, G.J.

N1 - Conference code: 14

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

KW - Approximation

KW - Assignment problem

KW - Balanced optimization

KW - Computational complexity

UR - http://www.scopus.com/inward/record.url?scp=85010641861&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-51741-4_8

DO - 10.1007/978-3-319-51741-4_8

M3 - Conference contribution

AN - SCOPUS:85010641861

SN - 978-3-319-51740-7

T3 - Lecture Notes in Computer Science

SP - 92

EP - 102

BT - Approximation and Online Algorithms : 14th International Workshop, WAOA 2016, Revised Selected Papers

A2 - Jansen, K.

A2 - Mastrolilli, M.

PB - Springer

CY - Cham

T2 - 14th International Workshop on Approximation and Online Algorithms (WAOA 2016)

Y2 - 25 August 2016 through 26 August 2016

ER -

Balanced optimization with vector costs

Samenvatting

Publicatie series

Congres

Financiering

Toegang tot document

Andere bestanden en links

Vingerafdruk

Citeer dit