Timeline for Minimum length path touching $n$ circles
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 8, 2014 at 13:53 | comment | added | Joseph O'Rourke | "For example, the neighborhoods may be disks centered at buyers’ locations, and the radius of each disk specifies the maximum distance a buyer is willing to travel to the meeting place." | |
| Jul 8, 2014 at 13:41 | comment | added | Joseph O'Rourke | I think if you look at the paper I cited, you will find your problem is not different. Don't be misled by Fig.1. | |
| Jul 8, 2014 at 13:39 | comment | added | lchen | @JosephO'Rourke. Thanks. But my problem is different from TSP with neighbor. I am looking for a path (that touches each circle) shorter than the path that connects the centers of each circles. | |
| Jul 8, 2014 at 12:52 | history | edited | Joseph O'Rourke | CC BY-SA 3.0 |
added 8 characters in body
|
| Jul 8, 2014 at 12:50 | comment | added | Joseph O'Rourke | @EmilJeřábek: I stand corrected---Thanks. (Altered the language to avoid misleading.) | |
| Jul 8, 2014 at 12:48 | comment | added | Emil Jeřábek | PTAS implies an approximation ratio arbitrarily close to 1. There is more than one algorithm in their paper, the PTAS algorithm is different from the 3.55 algorithm. | |
| Jul 8, 2014 at 12:05 | history | edited | Joseph O'Rourke | CC BY-SA 3.0 |
added 60 characters in body
|
| Jul 8, 2014 at 12:00 | history | answered | Joseph O'Rourke | CC BY-SA 3.0 |