# The Reward-Penalty-Selection Problem

Source: [The Reward-Penalty-Selection Problem](<https://www.sota2.com/research/paper/68fa6a421e209131cea2710a>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T23:20:37.043Z

Authors: T. Heller, S.O. Krumke, K.-H. K\\"ufer

Published: 2021-06-28T12:12:02.000Z

## Abstract

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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2106.14601>)

[PDF](<https://arxiv.org/pdf/2106.14601.pdf>)
