2021/06/28 by Till Heller, Heller, T., Sven O. Krumke +3
Computer Science · Economics, Econometrics and Finance · #68Q25 #90C27 #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.2106.14601
openalex publication_date 2021/06/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Set Cover Problem (SCP) and the Hitting Set Problem (HSP) are well-studied optimization problems. In this paper we introduce the Reward-Penalty-Selection Problem (RPSP) which can be understood as a combination of the SCP and the HSP where the objectives of both problems are contrary to each other. Applications of the RPSP can be found in the context of combinatorial exchanges in order to solve the corresponding winner determination problem. We give complexity results for the minimization and the maximization problem as well as for several variants with additional restrictions. Further, we provide an algorithm that runs in polynomial time for the special case of laminar sets and a dynamic programming approach for the case where the instance can be represented by a tree or a graph with bounded tree-width. We further present a graph theoretical generalization of this problem and results regarding its complexity.