Balanced optimization with vector costs

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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.

Original languageEnglish
Title of host publicationApproximation and Online Algorithms : 14th International Workshop, WAOA 2016, Revised Selected Papers
EditorsK. Jansen, M. Mastrolilli
Place of PublicationCham
PublisherSpringer
Pages92-102
Number of pages11
ISBN (Electronic)978-3-319-51741-4
ISBN (Print)978-3-319-51740-7
DOIs
Publication statusPublished - 2017
Event14th International Workshop on Approximation and Online Algorithms (WAOA 2016) - Lakeside Lecture Theatres ("Søauditorierne") at Aarhus University, Aarhus, Denmark
Duration: 25 Aug 201626 Aug 2016
Conference number: 14
http://conferences.au.dk/algo16/waoa/
http://conferences.au.dk/algo16/travel-and-local-information/

Publication series

NameLecture Notes in Computer Science
Volume10138
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th International Workshop on Approximation and Online Algorithms (WAOA 2016)
Abbreviated titleWOA 2016
CountryDenmark
CityAarhus
Period25/08/1626/08/16
Internet address

Keywords

  • Approximation
  • Assignment problem
  • Balanced optimization
  • Computational complexity

Fingerprint Dive into the research topics of 'Balanced optimization with vector costs'. Together they form a unique fingerprint.

Cite this