𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Approximation algorithms for group prize-collecting and location-routing problems

✍ Scribed by Hagai Glicksman; Michal Penn

Book ID
108112768
Publisher
Elsevier Science
Year
2008
Tongue
English
Weight
551 KB
Volume
156
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

A better approximation algorithm for the
A better approximation algorithm for the budget prize collecting tree problem
✍ Asaf Levin πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 206 KB

Given an undirected graph G = (V; E), an edge cost c(e) ¿ 0 for each edge e ∈ E, a vertex prize p(v) ¿ 0 for each vertex v ∈ V , and an edge budget B. The BUDGET PRIZE COLLECTING TREE PROBLEM is to ÿnd a subtree T = (V ; E ) that maximizes v∈V p(v), subject to e∈E c(e) 6 B. We present a (4 + )-appro

Approximation algorithms for the watchma
Approximation algorithms for the watchman route and zookeeper's problems
✍ Xuehou Tan πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 261 KB

Given a simple polygon P with n vertices and a starting point s on its boundary, the watchman route problem asks for a shortest route in P through s such that each point in the interior of the polygon can be seen from at least one point along the route. In this paper, we present a simple, linear-tim

A branch-and-cut algorithm for the undir
A branch-and-cut algorithm for the undirected prize collecting traveling salesman problem
✍ Jean-FranΓ§ois BΓ©rubΓ©; Michel Gendreau; Jean-Yves Potvin πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 130 KB πŸ‘ 1 views

## Abstract Given an undirected graph with edge costs and vertex prizes, the aim of the Prize Collecting Traveling Salesman Problem (PCTSP) is to find a simple cycle minimizing the total edge cost while collecting at least a minimum amount of prizes. In this article, we present a branch‐and‐cut alg