Balanced optimization with vector costs

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

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

1 Citation (Scopus)

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
Country/TerritoryDenmark
CityAarhus
Period25/08/1626/08/16
Internet address

Funding

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.

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