Maximizing the Margin between Desirable and Undesirable Elements in a Covering Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911291223834624 |
|---|---|
| author | Boileau, Sophie Hong, Andrew Liben-Nowell, David Pattison, Alistair Rafferty, Anna N. Roslansky, Charlie |
| author_facet | Boileau, Sophie Hong, Andrew Liben-Nowell, David Pattison, Alistair Rafferty, Anna N. Roslansky, Charlie |
| contents | In many covering settings, it is natural to consider the presence both of elements that we seek to include and of elements that we seek to avoid. This paper introduces a novel combinatorial problem formalizing this tradeoff: from a collection of sets containing both "desirable" and "undesirable" items, pick the subcollection that maximizes the margin between the number of desirable and undesirable elements covered. We call this the Target Approximation Problem (TAP) and argue that many real-world scenarios are naturally modeled via this objective. We first show that TAP is hard, even when restricted to cases where the given sets are small or where elements appear in only a small number of sets. In a large swath of these cases, we show that TAP is hard even to approximate. We then exhibit exact polynomial-time algorithms for other restricted cases and provide an efficient 0.5-approximation for the case where elements occur at most twice, derived through a tight connection to the greedy algorithm for Unweighted Set Cover. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_03817 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Maximizing the Margin between Desirable and Undesirable Elements in a Covering Problem Boileau, Sophie Hong, Andrew Liben-Nowell, David Pattison, Alistair Rafferty, Anna N. Roslansky, Charlie Data Structures and Algorithms In many covering settings, it is natural to consider the presence both of elements that we seek to include and of elements that we seek to avoid. This paper introduces a novel combinatorial problem formalizing this tradeoff: from a collection of sets containing both "desirable" and "undesirable" items, pick the subcollection that maximizes the margin between the number of desirable and undesirable elements covered. We call this the Target Approximation Problem (TAP) and argue that many real-world scenarios are naturally modeled via this objective. We first show that TAP is hard, even when restricted to cases where the given sets are small or where elements appear in only a small number of sets. In a large swath of these cases, we show that TAP is hard even to approximate. We then exhibit exact polynomial-time algorithms for other restricted cases and provide an efficient 0.5-approximation for the case where elements occur at most twice, derived through a tight connection to the greedy algorithm for Unweighted Set Cover. |
| title | Maximizing the Margin between Desirable and Undesirable Elements in a Covering Problem |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2507.03817 |