Universität zu Köln

Bampis, Evripidis, Escoffier, Bruno, Schewior, Kevin and Teiller, Alexandre (2021). Online Multistage Subset Maximization Problems. Algorithmica, 83 (8). S. 2374 - 2400. NEW YORK: SPRINGER. ISSN 1432-0541

Full text not available from this repository.

Abstract

Numerous combinatorial optimization problems (knapsack, maximum-weight matching, etc.) can be expressed as subset maximization problems: One is given a ground set N = {1,., n}, a collection F subset of 2(N) of subsets thereof such that empty set is an element of F, and an objective (profit) function p : F -> R+. The task is to choose a set S is an element of F that maximizes p(S). We consider the multistage version (Eisenstat et al., Gupta et al., both ICALP 2014) of such problems: The profit function p(t) (and possibly the set of feasible solutions F-t) may change over time. Since in many applications changing the solution is costly, the task becomes to find a sequence of solutions that optimizes the trade-off between good per-time solutions and stable solutions taking into account an additional similarity bonus. As similarity measure for two consecutive solutions, we consider either the size of the intersection of the two solutions or the difference of n and the Hamming distance between the two characteristic vectors. We study multistage subset maximization problems in the online setting, that is, p(t) (along with possibly F-t) only arrive one by one and, upon such an arrival, the online algorithm has to output the corresponding solution without knowledge of the future. We develop general techniques for online multistage subset maximization and thereby characterize those models (given by the type of data evolution and the type of similarity measure) that admit a constant-competitive online algorithm. When no constant competitive ratio is possible, we employ lookahead to circumvent this issue. When a constant competitive ratio is possible, we provide almost matching lower and upper bounds on the best achievable one.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Bampis, Evripidis UNSPECIFIED UNSPECIFIED UNSPECIFIED Escoffier, Bruno UNSPECIFIED UNSPECIFIED UNSPECIFIED Schewior, Kevin UNSPECIFIED UNSPECIFIED UNSPECIFIED Teiller, Alexandre UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-586183
DOI:	10.1007/s00453-021-00834-7
Journal or Publication Title:	Algorithmica
Volume:	83
Number:	8
Page Range:	S. 2374 - 2400
Date:	2021
Publisher:	SPRINGER
Place of Publication:	NEW YORK
ISSN:	1432-0541
Language:	English
Faculty:	Unspecified
Divisions:	Unspecified
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language Computer Science, Software Engineering; Mathematics, Applied Multiple languages
URI:	http://kups.ub.uni-koeln.de/id/eprint/58618