Title	Balanced Optimization with vector costs
Creator	Spieksma, Frits
Publisher	Banff International Research Station for Mathematical Innovation and Discovery
Date Issued	2015-11-30T11:43
Description	We consider so-called balanced optimization problems with vector costs. We pro- pose a framework containing such problems; this framework allows us to investigate the complexity and approximability of these problems in a general setting. More concrete, each problem in the framework admits a 2-approximation, and for many problems within the framework this result is best-possible, in the sense that having a polynomial-time algorithm with a performance ratio better than 2 would imply P=NP. Special attention is paid to the balanced assignment problem with vector costs: we show that the problem remains NP-hard even in case of sum costs. This is joint work with Annette Ficker and Gerhard Woeginger
Extent	26 minutes
Subject	Mathematics; Computer science; Combinatorics; Theoretical computer science
Type	Moving Image
File Format	video/mp4
Language	eng
Notes	Author affiliation: Katholieke Universiteit Leuven
Series	BIRS Workshop Lecture Videos (Banff, Alta)
Date Available	2016-05-31
Provider	Vancouver : University of British Columbia Library
Rights	Attribution-NonCommercial-NoDerivatives 4.0 International
DOI	10.14288/1.0303472
URI	http://hdl.handle.net/2429/58207
Affiliation	Non UBC
Peer Review Status	Unreviewed
Scholarly Level	Faculty
Rights URI	http://creativecommons.org/licenses/by-nc-nd/4.0/
Aggregated Source Repository	DSpace

Open Collections

BIRS Workshop Lecture Videos

Balanced Optimization with vector costs Spieksma, Frits

Description

Item Metadata

Item Media

Item Citations and Data

Rights