Robust balanced optimization

An instance of a balanced optimization problem with vector costs consists of a ground set X, a cost-vector for every element of X, and a system of feasible subsets over X. The goal is to find a feasible subset that minimizes the so-called imbalance of values in every coordinate of the underlying vec...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	AnnetteM.C. Ficker, FritsC.R. Spieksma, GerhardJ. Woeginger
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2018
Materias:	90C27 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/00b633709f694b8d960c4cc77e9ef442
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:00b633709f694b8d960c4cc77e9ef442
record_format	dspace
spelling	oai:doaj.org-article:00b633709f694b8d960c4cc77e9ef4422021-12-02T05:01:07ZRobust balanced optimization2192-440610.1007/s13675-018-0093-yhttps://doaj.org/article/00b633709f694b8d960c4cc77e9ef4422018-09-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621001027https://doaj.org/toc/2192-4406An instance of a balanced optimization problem with vector costs consists of a ground set X, a cost-vector for every element of X, and a system of feasible subsets over X. The goal is to find a feasible subset that minimizes the so-called imbalance of values in every coordinate of the underlying vector costs. Balanced optimization problems with vector costs are equivalent to the robust optimization version of balanced optimization problems under the min-max criterion. We regard these problems as a family of optimization problems; one particular member of this family is the known balanced assignment problem. We investigate the complexity and approximability of robust 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). We pay special attention to the balanced assignment problem with vector costs and show that this problem is NP-hard even in the highly restricted case of sum costs. We conclude by performing computational experiments for this problem.AnnetteM.C. FickerFritsC.R. SpieksmaGerhardJ. WoegingerElsevierarticle90C27Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 6, Iss 3, Pp 239-266 (2018)
institution	DOAJ
collection	DOAJ
language	EN
topic	90C27 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	90C27 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 AnnetteM.C. Ficker FritsC.R. Spieksma GerhardJ. Woeginger Robust balanced optimization
description	An instance of a balanced optimization problem with vector costs consists of a ground set X, a cost-vector for every element of X, and a system of feasible subsets over X. The goal is to find a feasible subset that minimizes the so-called imbalance of values in every coordinate of the underlying vector costs. Balanced optimization problems with vector costs are equivalent to the robust optimization version of balanced optimization problems under the min-max criterion. We regard these problems as a family of optimization problems; one particular member of this family is the known balanced assignment problem. We investigate the complexity and approximability of robust 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). We pay special attention to the balanced assignment problem with vector costs and show that this problem is NP-hard even in the highly restricted case of sum costs. We conclude by performing computational experiments for this problem.
format	article
author	AnnetteM.C. Ficker FritsC.R. Spieksma GerhardJ. Woeginger
author_facet	AnnetteM.C. Ficker FritsC.R. Spieksma GerhardJ. Woeginger
author_sort	AnnetteM.C. Ficker
title	Robust balanced optimization
title_short	Robust balanced optimization
title_full	Robust balanced optimization
title_fullStr	Robust balanced optimization
title_full_unstemmed	Robust balanced optimization
title_sort	robust balanced optimization
publisher	Elsevier
publishDate	2018
url	https://doaj.org/article/00b633709f694b8d960c4cc77e9ef442
work_keys_str_mv	AT annettemcficker robustbalancedoptimization AT fritscrspieksma robustbalancedoptimization AT gerhardjwoeginger robustbalancedoptimization
_version_	1718400809700425728

Robust balanced optimization

Ejemplares similares