A better-than-1.6-approximation for prize-collecting TSP Article Swipe

PDF

Jannis Blauth , Nathan Klein , Martin Nägele ·

YOU? · · 2025 · Open Access · · DOI: https://doi.org/10.1007/s10107-025-02221-4

Prize-Collecting TSP is a variant of the traveling salesperson problem where one may drop vertices from the tour at the cost of vertex-dependent penalties. The quality of a solution is then measured by adding the length of the tour and the sum of all penalties of vertices that are not visited. We present a polynomial-time approximation algorithm with an approximation guarantee slightly below 1.6, where the guarantee is with respect to the natural linear programming relaxation of the problem. This improves upon the previous best-known approximation ratio of 1.774. Our approach is based on a known decomposition for solutions of this linear relaxation into rooted trees. Our algorithm takes a tree from this decomposition and then performs a pruning step before doing parity correction on the remainder. Using a simple analysis, we bound the approximation guarantee of the proposed algorithm by $$(1+\sqrt{5})\big /2 \approx 1.618$$ , the golden ratio. With some additional technical care we further improve the approximation guarantee to 1.599. Furthermore, we show that for the path version of Prize-Collecting TSP (known as Prize-Collecting Stroll) our approach yields an approximation guarantee of 1.6662, improving upon the previous best-known guarantee of 1.926.

Related Topics

Mathematics

Numerical Analysis

Combinatorics

Mathematical Analysis

Concepts

Mathematics Numerical analysis Approximation algorithm Numerical approximation Combinatorics Mathematical optimization Applied mathematics Mathematical analysis

Metadata

Type: article
Language: en
Landing Page: https://doi.org/10.1007/s10107-025-02221-4
PDF: https://link.springer.com/content/pdf/10.1007/s10107-025-02221-4.pdf
OA Status: hybrid
References: 39
Related Works: 10
OpenAlex ID: https://openalex.org/W4410291403

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4410291403

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.1007/s10107-025-02221-4

Digital Object Identifier
Title: A better-than-1.6-approximation for prize-collecting TSP

Work title
Type: article

OpenAlex work type
Language: en

Primary language
Publication year: 2025

Year of publication
Publication date: 2025-05-12

Full publication date if available
Authors: Jannis Blauth, Nathan Klein, Martin Nägele

List of authors in order
Landing page: https://doi.org/10.1007/s10107-025-02221-4

Publisher landing page
PDF URL: https://link.springer.com/content/pdf/10.1007/s10107-025-02221-4.pdf

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: hybrid

Open access status per OpenAlex
OA URL: https://link.springer.com/content/pdf/10.1007/s10107-025-02221-4.pdf

Direct OA link when available
Concepts: Mathematics, Numerical analysis, Approximation algorithm, Numerical approximation, Combinatorics, Mathematical optimization, Applied mathematics, Mathematical analysis

Top concepts (fields/topics) attached by OpenAlex
Cited by: 0

Total citation count in OpenAlex
References (count): 39

Number of works referenced by this work
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4410291403
doi	https://doi.org/10.1007/s10107-025-02221-4
ids.doi	https://doi.org/10.1007/s10107-025-02221-4
ids.openalex	https://openalex.org/W4410291403
fwci	0.0
type	article
title	A better-than-1.6-approximation for prize-collecting TSP
awards[0].id	https://openalex.org/G2405319508
awards[0].funder_id	https://openalex.org/F4320320924
awards[0].display_name
awards[0].funder_award_id	P500PT_206742
awards[0].funder_display_name	Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung
awards[1].id	https://openalex.org/G6150757402
awards[1].funder_id	https://openalex.org/F4320338279
awards[1].display_name
awards[1].funder_award_id	FA9550-20-1-0212
awards[1].funder_display_name	Air Force Office of Scientific Research
awards[2].id	https://openalex.org/G5512240048
awards[2].funder_id	https://openalex.org/F4320320879
awards[2].display_name
awards[2].funder_award_id	EXZ-2047/1 – 390685813
awards[2].funder_display_name	Deutsche Forschungsgemeinschaft
awards[3].id	https://openalex.org/G3427691308
awards[3].funder_id	https://openalex.org/F4320306076
awards[3].display_name
awards[3].funder_award_id	CCF-1813135
awards[3].funder_display_name	National Science Foundation
awards[4].id	https://openalex.org/G8497923736
awards[4].funder_id	https://openalex.org/F4320306076
awards[4].display_name
awards[4].funder_award_id	DGE-1762114
awards[4].funder_display_name	National Science Foundation
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T12288
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9997000098228455
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1705
topics[0].subfield.display_name	Computer Networks and Communications
topics[0].display_name	Optimization and Search Problems
topics[1].id	https://openalex.org/T10586
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9983000159263611
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1707
topics[1].subfield.display_name	Computer Vision and Pattern Recognition
topics[1].display_name	Robotic Path Planning Algorithms
topics[2].id	https://openalex.org/T10567
topics[2].field.id	https://openalex.org/fields/22
topics[2].field.display_name	Engineering
topics[2].score	0.9979000091552734
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/2209
topics[2].subfield.display_name	Industrial and Manufacturing Engineering
topics[2].display_name	Vehicle Routing Optimization Methods
funders[0].id	https://openalex.org/F4320306076
funders[0].ror	https://ror.org/021nxhr62
funders[0].display_name	National Science Foundation
funders[1].id	https://openalex.org/F4320320879
funders[1].ror	https://ror.org/018mejw64
funders[1].display_name	Deutsche Forschungsgemeinschaft
funders[2].id	https://openalex.org/F4320320924
funders[2].ror	https://ror.org/00yjd3n13
funders[2].display_name	Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung
funders[3].id	https://openalex.org/F4320338279
funders[3].ror	https://ror.org/011e9bt93
funders[3].display_name	Air Force Office of Scientific Research
is_xpac	False
apc_list.value	2190
apc_list.currency	EUR
apc_list.value_usd	2890
apc_paid.value	2190
apc_paid.currency	EUR
apc_paid.value_usd	2890
concepts[0].id	https://openalex.org/C33923547
concepts[0].level	0
concepts[0].score	0.6843045949935913
concepts[0].wikidata	https://www.wikidata.org/wiki/Q395
concepts[0].display_name	Mathematics
concepts[1].id	https://openalex.org/C48753275
concepts[1].level	2
concepts[1].score	0.5285314917564392
concepts[1].wikidata	https://www.wikidata.org/wiki/Q11216
concepts[1].display_name	Numerical analysis
concepts[2].id	https://openalex.org/C148764684
concepts[2].level	2
concepts[2].score	0.4650036096572876
concepts[2].wikidata	https://www.wikidata.org/wiki/Q621751
concepts[2].display_name	Approximation algorithm
concepts[3].id	https://openalex.org/C2986878899
concepts[3].level	3
concepts[3].score	0.4304547905921936
concepts[3].wikidata	https://www.wikidata.org/wiki/Q11216
concepts[3].display_name	Numerical approximation
concepts[4].id	https://openalex.org/C114614502
concepts[4].level	1
concepts[4].score	0.3593922555446625
concepts[4].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[4].display_name	Combinatorics
concepts[5].id	https://openalex.org/C126255220
concepts[5].level	1
concepts[5].score	0.3393641710281372
concepts[5].wikidata	https://www.wikidata.org/wiki/Q141495
concepts[5].display_name	Mathematical optimization
concepts[6].id	https://openalex.org/C28826006
concepts[6].level	1
concepts[6].score	0.3372911810874939
concepts[6].wikidata	https://www.wikidata.org/wiki/Q33521
concepts[6].display_name	Applied mathematics
concepts[7].id	https://openalex.org/C134306372
concepts[7].level	1
concepts[7].score	0.1313476264476776
concepts[7].wikidata	https://www.wikidata.org/wiki/Q7754
concepts[7].display_name	Mathematical analysis
keywords[0].id	https://openalex.org/keywords/mathematics
keywords[0].score	0.6843045949935913
keywords[0].display_name	Mathematics
keywords[1].id	https://openalex.org/keywords/numerical-analysis
keywords[1].score	0.5285314917564392
keywords[1].display_name	Numerical analysis
keywords[2].id	https://openalex.org/keywords/approximation-algorithm
keywords[2].score	0.4650036096572876
keywords[2].display_name	Approximation algorithm
keywords[3].id	https://openalex.org/keywords/numerical-approximation
keywords[3].score	0.4304547905921936
keywords[3].display_name	Numerical approximation
keywords[4].id	https://openalex.org/keywords/combinatorics
keywords[4].score	0.3593922555446625
keywords[4].display_name	Combinatorics
keywords[5].id	https://openalex.org/keywords/mathematical-optimization
keywords[5].score	0.3393641710281372
keywords[5].display_name	Mathematical optimization
keywords[6].id	https://openalex.org/keywords/applied-mathematics
keywords[6].score	0.3372911810874939
keywords[6].display_name	Applied mathematics
keywords[7].id	https://openalex.org/keywords/mathematical-analysis
keywords[7].score	0.1313476264476776
keywords[7].display_name	Mathematical analysis
language	en
locations[0].id	doi:10.1007/s10107-025-02221-4
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S193920097
locations[0].source.issn	0025-5610, 1436-4646
locations[0].source.type	journal
locations[0].source.is_oa	False
locations[0].source.issn_l	0025-5610
locations[0].source.is_core	True
locations[0].source.is_in_doaj	False
locations[0].source.display_name	Mathematical Programming
locations[0].source.host_organization	https://openalex.org/P4310319900
locations[0].source.host_organization_name	Springer Science+Business Media
locations[0].source.host_organization_lineage	https://openalex.org/P4310319900, https://openalex.org/P4310319965
locations[0].source.host_organization_lineage_names	Springer Science+Business Media, Springer Nature
locations[0].license	cc-by
locations[0].pdf_url	https://link.springer.com/content/pdf/10.1007/s10107-025-02221-4.pdf
locations[0].version	publishedVersion
locations[0].raw_type	journal-article
locations[0].license_id	https://openalex.org/licenses/cc-by
locations[0].is_accepted	True
locations[0].is_published	True
locations[0].raw_source_name	Mathematical Programming
locations[0].landing_page_url	https://doi.org/10.1007/s10107-025-02221-4
indexed_in	crossref
authorships[0].author.id	https://openalex.org/A5031102399
authorships[0].author.orcid	https://orcid.org/0000-0001-5181-802X
authorships[0].author.display_name	Jannis Blauth
authorships[0].author_position	first
authorships[0].raw_author_name	Jannis Blauth
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5014157604
authorships[1].author.orcid	https://orcid.org/0009-0003-4052-5864
authorships[1].author.display_name	Nathan Klein
authorships[1].author_position	middle
authorships[1].raw_author_name	Nathan Klein
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5027137195
authorships[2].author.orcid	https://orcid.org/0000-0002-3059-6402
authorships[2].author.display_name	Martin Nägele
authorships[2].author_position	last
authorships[2].raw_author_name	Martin Nägele
authorships[2].is_corresponding	False
has_content.pdf	True
has_content.grobid_xml	True
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://link.springer.com/content/pdf/10.1007/s10107-025-02221-4.pdf
open_access.oa_status	hybrid
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	A better-than-1.6-approximation for prize-collecting TSP
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T03:46:38.306776
primary_topic.id	https://openalex.org/T12288
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9997000098228455
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1705
primary_topic.subfield.display_name	Computer Networks and Communications
primary_topic.display_name	Optimization and Search Problems
related_works	https://openalex.org/W1997932535, https://openalex.org/W2010049312, https://openalex.org/W1970786191, https://openalex.org/W4402809589, https://openalex.org/W2963771406, https://openalex.org/W2152819099, https://openalex.org/W2023399328, https://openalex.org/W2162623007, https://openalex.org/W2061012261, https://openalex.org/W2009695399
cited_by_count	0
locations_count	1
best_oa_location.id	doi:10.1007/s10107-025-02221-4
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S193920097
best_oa_location.source.issn	0025-5610, 1436-4646
best_oa_location.source.type	journal
best_oa_location.source.is_oa	False
best_oa_location.source.issn_l	0025-5610
best_oa_location.source.is_core	True
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	Mathematical Programming
best_oa_location.source.host_organization	https://openalex.org/P4310319900
best_oa_location.source.host_organization_name	Springer Science+Business Media
best_oa_location.source.host_organization_lineage	https://openalex.org/P4310319900, https://openalex.org/P4310319965
best_oa_location.source.host_organization_lineage_names	Springer Science+Business Media, Springer Nature
best_oa_location.license	cc-by
best_oa_location.pdf_url	https://link.springer.com/content/pdf/10.1007/s10107-025-02221-4.pdf
best_oa_location.version	publishedVersion
best_oa_location.raw_type	journal-article
best_oa_location.license_id	https://openalex.org/licenses/cc-by
best_oa_location.is_accepted	True
best_oa_location.is_published	True
best_oa_location.raw_source_name	Mathematical Programming
best_oa_location.landing_page_url	https://doi.org/10.1007/s10107-025-02221-4
primary_location.id	doi:10.1007/s10107-025-02221-4
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S193920097
primary_location.source.issn	0025-5610, 1436-4646
primary_location.source.type	journal
primary_location.source.is_oa	False
primary_location.source.issn_l	0025-5610
primary_location.source.is_core	True
primary_location.source.is_in_doaj	False
primary_location.source.display_name	Mathematical Programming
primary_location.source.host_organization	https://openalex.org/P4310319900
primary_location.source.host_organization_name	Springer Science+Business Media
primary_location.source.host_organization_lineage	https://openalex.org/P4310319900, https://openalex.org/P4310319965
primary_location.source.host_organization_lineage_names	Springer Science+Business Media, Springer Nature
primary_location.license	cc-by
primary_location.pdf_url	https://link.springer.com/content/pdf/10.1007/s10107-025-02221-4.pdf
primary_location.version	publishedVersion
primary_location.raw_type	journal-article
primary_location.license_id	https://openalex.org/licenses/cc-by
primary_location.is_accepted	True
primary_location.is_published	True
primary_location.raw_source_name	Mathematical Programming
primary_location.landing_page_url	https://doi.org/10.1007/s10107-025-02221-4
publication_date	2025-05-12
publication_year	2025
referenced_works	https://openalex.org/W4390575860, https://openalex.org/W4399521223, https://openalex.org/W2240814884, https://openalex.org/W2123087902, https://openalex.org/W4396882112, https://openalex.org/W4300273322, https://openalex.org/W1760833224, https://openalex.org/W1986056047, https://openalex.org/W1980942794, https://openalex.org/W4237504351, https://openalex.org/W2044119054, https://openalex.org/W4398172548, https://openalex.org/W4376639517, https://openalex.org/W2113939799, https://openalex.org/W2115556222, https://openalex.org/W2117226423, https://openalex.org/W3212127876, https://openalex.org/W2064284095, https://openalex.org/W2017501272, https://openalex.org/W2038190710, https://openalex.org/W2001139415, https://openalex.org/W4249586771, https://openalex.org/W3167350281, https://openalex.org/W4377200004, https://openalex.org/W2962875727, https://openalex.org/W2643346538, https://openalex.org/W1986334784, https://openalex.org/W1786780942, https://openalex.org/W2148319529, https://openalex.org/W1483203801, https://openalex.org/W2117443767, https://openalex.org/W2994566040, https://openalex.org/W4311156467, https://openalex.org/W2250014226, https://openalex.org/W2964044445, https://openalex.org/W3205213369, https://openalex.org/W3014100174, https://openalex.org/W3046251504, https://openalex.org/W3099932027
referenced_works_count	39
abstract_inverted_index.,	164
abstract_inverted_index.a	4, 28, 54, 95, 110, 118, 129
abstract_inverted_index./2	143
abstract_inverted_index.We	52
abstract_inverted_index.an	59, 199
abstract_inverted_index.as	193
abstract_inverted_index.at	19
abstract_inverted_index.by	33, 141
abstract_inverted_index.is	3, 30, 68, 92
abstract_inverted_index.of	6, 22, 27, 37, 43, 46, 77, 88, 100, 137, 189, 202, 210
abstract_inverted_index.on	94, 125
abstract_inverted_index.to	71, 179
abstract_inverted_index.we	132, 173, 182
abstract_inverted_index.Our	90, 107
abstract_inverted_index.TSP	2, 191
abstract_inverted_index.The	25
abstract_inverted_index.all	44
abstract_inverted_index.and	40, 115
abstract_inverted_index.are	49
abstract_inverted_index.for	98, 185
abstract_inverted_index.may	13
abstract_inverted_index.not	50
abstract_inverted_index.one	12
abstract_inverted_index.our	196
abstract_inverted_index.sum	42
abstract_inverted_index.the	7, 17, 20, 35, 38, 41, 66, 72, 78, 83, 126, 134, 138, 165, 176, 186, 206
abstract_inverted_index.1.6,	64
abstract_inverted_index.This	80
abstract_inverted_index.With	168
abstract_inverted_index.care	172
abstract_inverted_index.cost	21
abstract_inverted_index.drop	14
abstract_inverted_index.from	16, 112
abstract_inverted_index.into	104
abstract_inverted_index.path	187
abstract_inverted_index.show	183
abstract_inverted_index.some	169
abstract_inverted_index.step	120
abstract_inverted_index.that	48, 184
abstract_inverted_index.then	31, 116
abstract_inverted_index.this	101, 113
abstract_inverted_index.tour	18, 39
abstract_inverted_index.tree	111
abstract_inverted_index.upon	82, 205
abstract_inverted_index.with	58, 69
abstract_inverted_index.Using	128
abstract_inverted_index.based	93
abstract_inverted_index.below	63
abstract_inverted_index.bound	133
abstract_inverted_index.doing	122
abstract_inverted_index.known	96
abstract_inverted_index.ratio	87
abstract_inverted_index.takes	109
abstract_inverted_index.where	11, 65
abstract_inverted_index.(known	192
abstract_inverted_index.1.599.	180
abstract_inverted_index.1.774.	89
abstract_inverted_index.1.926.	211
abstract_inverted_index.adding	34
abstract_inverted_index.before	121
abstract_inverted_index.golden	166
abstract_inverted_index.length	36
abstract_inverted_index.linear	74, 102
abstract_inverted_index.parity	123
abstract_inverted_index.ratio.	167
abstract_inverted_index.rooted	105
abstract_inverted_index.simple	130
abstract_inverted_index.trees.	106
abstract_inverted_index.yields	198
abstract_inverted_index.1.618$$	145
abstract_inverted_index.1.6662,	203
abstract_inverted_index.Stroll)	195
abstract_inverted_index.\approx	144
abstract_inverted_index.further	174
abstract_inverted_index.improve	175
abstract_inverted_index.natural	73
abstract_inverted_index.present	53
abstract_inverted_index.problem	10
abstract_inverted_index.pruning	119
abstract_inverted_index.quality	26
abstract_inverted_index.respect	70
abstract_inverted_index.variant	5
abstract_inverted_index.version	188
abstract_inverted_index.Abstract	0
abstract_inverted_index.approach	91, 197
abstract_inverted_index.improves	81
abstract_inverted_index.measured	32
abstract_inverted_index.performs	117
abstract_inverted_index.previous	84, 207
abstract_inverted_index.problem.	79
abstract_inverted_index.proposed	139
abstract_inverted_index.slightly	62
abstract_inverted_index.solution	29
abstract_inverted_index.vertices	15, 47
abstract_inverted_index.visited.	51
abstract_inverted_index.<mml:math	146
abstract_inverted_index.algorithm	57, 108, 140
abstract_inverted_index.analysis,	131
abstract_inverted_index.guarantee	61, 67, 136, 178, 201, 209
abstract_inverted_index.improving	204
abstract_inverted_index.penalties	45
abstract_inverted_index.solutions	99
abstract_inverted_index.technical	171
abstract_inverted_index.traveling	8
abstract_inverted_index.<mml:mrow>	148, 156
abstract_inverted_index.additional	170
abstract_inverted_index.best-known	85, 208
abstract_inverted_index.correction	124
abstract_inverted_index.penalties.	24
abstract_inverted_index.relaxation	76, 103
abstract_inverted_index.remainder.	127
abstract_inverted_index.</mml:math>	163
abstract_inverted_index.</mml:mrow>	158, 162
abstract_inverted_index.<mml:msqrt>	152
abstract_inverted_index.programming	75
abstract_inverted_index.salesperson	9
abstract_inverted_index.</mml:msqrt>	154
abstract_inverted_index.Furthermore,	181
abstract_inverted_index.approximation	56, 60, 86, 135, 177, 200
abstract_inverted_index.decomposition	97, 114
abstract_inverted_index.polynomial-time	55
abstract_inverted_index.Prize-Collecting	1, 190, 194
abstract_inverted_index.vertex-dependent	23
abstract_inverted_index.$$(1+\sqrt{5})\big	142
abstract_inverted_index.<mml:mn>1</mml:mn>	150
abstract_inverted_index.<mml:mn>2</mml:mn>	159
abstract_inverted_index.<mml:mn>5</mml:mn>	153
abstract_inverted_index.<mml:mo>(</mml:mo>	149
abstract_inverted_index.<mml:mo>)</mml:mo>	155
abstract_inverted_index.<mml:mo>+</mml:mo>	151
abstract_inverted_index.<mml:mo>/</mml:mo>	157
abstract_inverted_index.<mml:mo>≈</mml:mo>	160
abstract_inverted_index.<mml:mn>1.618</mml:mn>	161
abstract_inverted_index.xmlns:mml="http://www.w3.org/1998/Math/MathML">	147
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	3
citation_normalized_percentile.value	0.17716558
citation_normalized_percentile.is_in_top_1_percent	False
citation_normalized_percentile.is_in_top_10_percent	True