0
$\begingroup$

I have a metric space $(V,d)$ described by a tree $T$. And I have $k$ pair of vertices $\{s_i,t_i\}$ ($i \in [k]$) s.t. each of the vertices $s_i$ and $t_i$ are leaves of $T$. There is a car at one of the leaf $s$ of $T$. The car has to deliver a package from $s_i$ to $t_i$ (for each $i$). But at any time the car can hold $M$ messages. The car can drop messages it picked along the way and pick them up later. The aim is to find the walk of least cost starting and ending at $s$ and delivering all packages.

I am trying to prove (or disprove) that there exists a constant approximation where the car drops messages only at leaf nodes (i.e. it might drop message picked from $s_i$ at some leaf $w$, later pick it up and finally drop to destination $t_i$).

If I am not wrong not necessarily such an optimum exists and dropping messages in non-leaf nodes helps.


Source of the problem

My question is in relation to exercise $8.11$ from chapter $8$ of Design of Approximation Algorithms by Williamson and Shmoys. A part of the question asks assuming one has a constant factor approximation to the problem above for tree metrics, could one obtain a randomized $\mathcal{O}(\log{n})$ approximation for general metric spaces. I see that it follows trivially by using the randomized algorithm mentioned in the chapter (section $8.5$) to "approximate" a general metric space by a tree metric; except for subtle the point that the new "approximate" tree metric has additional vertices (all leaf nodes are from the original metric), where the car could drop and pick up messages. Having a solution (a walk) in the "approximate" tree metric, then to me doesn't seem to translate to an approximate solution in the original metric.

PS: Would appreciate hints only.

Improve this question
$\endgroup$
2
  • $\begingroup$ What's the context where you encountered this task? Can you credit the original source? How does the tree define a metric space? $\endgroup$
    – D.W. ♦
    May 14, 2022 at 3:53
  • 1
    $\begingroup$ Please don't put clarifications in the comments. Instead, edit your question to include all relevant information in the post, so people don't have to read the comments, and make sure it reads well for someone who encounters the question for the first time. Please provide a full citation, according to our requirements as listed here: cs.stackexchange.com/help/referencing, including title of the book, authors, and chapter/exercise number. This will help others with a similar question find this page via web search. $\endgroup$
    – D.W. ♦
    May 14, 2022 at 20:58

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.