PTAS and Exact Algorithms for $r$-Gathering Problems on Tree

Soh Kumabe; Takanori Maehara

arxiv: 1907.04087 · v1 · pith:FGDK2O7Wnew · submitted 2019-07-09 · 💻 cs.DS

PTAS and Exact Algorithms for r-Gathering Problems on Tree

Soh Kumabe , Takanori Maehara This is my paper

Pith reviewed 2026-05-25 00:05 UTC · model grok-4.3

classification 💻 cs.DS

keywords r-gatheringPTAStree metricfacility locationapproximation algorithmdynamic programmingNP-hard

0 comments

The pith

The r-gathering problem on tree metrics admits a polynomial-time approximation scheme.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that the minimum possible maximum user-to-facility distance in r-gathering can be approximated to within any factor 1+ε in polynomial time when the metric is a tree. This is significant because the problem is NP-hard even when restricted to spiders, a subclass of trees, and cannot be approximated better than factor 3 on arbitrary metrics. The tree structure is used to support dynamic programming that tracks assignments and openings while enforcing the minimum-r constraint per open facility. The same techniques yield PTAS results for several variants and exact polynomial algorithms for others.

Core claim

We give a PTAS for r-gathering problem on a tree. Furthermore, we give PTAS for some variants of the problems on a tree, and also give exact polynomial-time algorithms for another variants of r-gathering problem on a tree.

What carries the argument

Dynamic programming on the tree that decomposes the instance into subtrees while maintaining states for the number of assigned users and the maximum distance incurred so far.

If this is right

Any r-gathering instance on a tree can be solved to within (1+ε) of optimal for arbitrary ε>0 in polynomial time.
Multiple natural variants of r-gathering on trees also admit polynomial-time approximation schemes.
Other variants of r-gathering on trees admit exact optimal solutions in polynomial time.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same dynamic-programming approach may extend directly to graphs of bounded treewidth.
Practical implementations could solve moderate-sized tree networks exactly or nearly exactly for facility-location tasks with capacity-like constraints.
Similar PTAS results are unlikely on general metrics given the known 3-hardness.

Load-bearing premise

The input distances form a tree metric, which permits recursive decomposition of the problem into independent subproblems on subtrees.

What would settle it

A concrete tree instance together with an ε>0 on which the claimed algorithm either exceeds the (1+ε) guarantee or fails to run in the stated polynomial time bound.

read the original abstract

r-gathering problem is a variant of facility location problems. In this problem, we are given a set of users and a set of facilities on same metric space. We open some of the facilities and assign each user to an open facility, so that at least r users are assigned to every open facility. We aim to minimize the maximum distance between user and assigned facility. In general, this problem is NP-hard and admit an approximation algorithm with factor 3. It is known that the problem does not admit any approximation algorithm within a factor less than 3. In our another paper, we proved that this problem is NP-hard even on spider, which is a special case of tree metric. In this paper, we concentrate on the problems on a tree. First, we give a PTAS for r-gathering problem on a tree. Furthermore, we give PTAS for some variants of the problems on a tree, and also give exact polynomial-time algorithms for another variants of r-gathering problem on a tree.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper claims a PTAS plus some exact algorithms for r-gathering on trees, which fits known patterns for tree metrics but rests on an abstract with no technical details.

read the letter

The core claim here is a PTAS for r-gathering on trees, plus PTAS results for a few variants and exact polynomial-time algorithms for others. That is the main new piece relative to the 3-approximation known for general metrics and the NP-hardness already shown on spiders. Trees often admit dynamic programming that improves on general cases, so the direction makes sense on its face. The authors correctly note that the problem stays hard on spiders, which are a subclass of trees, yet still allow approximation schemes; that distinction is useful to record. The work is narrow but cleanly scoped to one metric class. Credit is due for separating the cases where exact solutions become feasible from those that need approximation. The abstract supplies no algorithm description, no running-time bounds, and no proof outline, so the actual technical strength cannot be judged from what is here. That is the main limitation at present. If the full paper contains a correct DP that respects the r-constraint and the tree structure without hidden exponential blow-up, the result is solid for the subfield. If the DP relies on standard subtree enumeration with careful bounding of facility choices, it would be routine but still worth publishing. This is for readers who work on facility location or approximation on graphs with special structure. Someone already familiar with tree DP for clustering or covering problems will see the value quickly. It is not a broad advance but fills a specific slot between the general-metric bound and the spider hardness. I would send it to peer review so that the algorithmic details can be checked by someone who knows the standard techniques for these problems.

Referee Report

1 major / 0 minor

Summary. The manuscript claims to give a PTAS for the r-gathering problem (minimize maximum user-facility distance subject to each open facility receiving at least r users) on tree metrics, PTASes for several variants, and exact polynomial-time algorithms for other variants. It recalls that the problem is NP-hard even on spiders (a subclass of trees) and admits a 3-approximation in general metrics but no better factor.

Significance. If the algorithmic claims hold, the results would establish that tree structure permits PTAS constructions (presumably via dynamic programming on subtrees) for an NP-hard facility-location variant while also identifying polynomially solvable special cases. This would be a useful addition to the literature on approximation algorithms for location problems restricted to tree metrics.

major comments (1)

[Abstract] Abstract: the central claims (existence of a PTAS, PTASes for variants, and exact poly-time algorithms) are stated without any algorithmic description, proof sketch, running-time bound, or reduction, so the soundness of the results cannot be assessed from the manuscript.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their review. We address the single major comment below.

read point-by-point responses

Referee: [Abstract] Abstract: the central claims (existence of a PTAS, PTASes for variants, and exact poly-time algorithms) are stated without any algorithmic description, proof sketch, running-time bound, or reduction, so the soundness of the results cannot be assessed from the manuscript.

Authors: Abstracts are intentionally concise high-level summaries and do not contain technical details such as algorithmic descriptions or running times; those appear in the body of the manuscript. Section 3 presents the PTAS via dynamic programming over subtrees of the input tree (with a running time of the form n^{O(1/ε)}), including the key recurrence, proof of correctness, and approximation guarantee. Sections 4 and 5 give analogous DP constructions for the listed variants together with the exact polynomial-time algorithms for the polynomially solvable special cases. We are happy to expand the abstract with a one-sentence pointer to the DP approach if the editor prefers. revision: partial

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper presents constructive PTAS and exact polynomial-time algorithms for r-gathering and its variants on trees. These are algorithmic results relying on standard tree DP decompositions that exploit the input metric structure directly. The sole self-citation is to a separate hardness proof on spiders and is used only for context, not as a load-bearing step in deriving the PTAS or exact algorithms. No equations reduce by construction to fitted inputs, no uniqueness theorems are imported from prior author work, and no ansatzes or renamings of known results appear. The derivation chain is self-contained and independent of the cited hardness result.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Claims rest on the domain assumption that tree metrics admit efficient combination of subproblems via dynamic programming or similar techniques; no free parameters or invented entities are introduced in the abstract.

axioms (1)

domain assumption Tree metrics admit efficient dynamic programming for facility-location-type problems.
The paper restricts to trees precisely to obtain PTAS and exact algorithms.

pith-pipeline@v0.9.0 · 5706 in / 1073 out tokens · 34017 ms · 2026-05-25T00:05:01.339064+00:00 · methodology