5 ms·
The issue isn't about approximating a TSP instance, but ensuring that points aren't too far apart from each other, even at the cost of increasing total length.
by modalduality 9y ago
The issue isn't about approximating a TSP instance, but ensuring that points aren't too far apart from each other, even at the cost of increasing total length.
I can't immediately think of a reduction that would factor this in so the best thing may be to just reduce this to the appropriate ILP instance and use a mixed ILP approximator like GLPK (or Gurobi is free for students too).
Incidentally, achieving a polynomially-sized ILP formulation for TSP isn't quite obvious. Wikipedia has a good explanation of how to do this: https://en.wikipedia.org/wiki/Travelling_salesman_problem#Integer_linear_programming_formulation https://en.wikipedia.org/wiki/Travelling_salesman_problem#In.... I'm not sure if the metric TSP has a simpler formulation.
Edit: Now that I think about it, it may be difficult to express the constraint that edges should be balanced out in a linear way. I happened to write about a similar problem a while ago (https://modalduality.org/posts/optimizing-color-coding/ https://modalduality.org/posts/optimizing-color-coding/), I ended up giving up on finding a linear formulation and went for sequential least squares instead.
- deleted 9y ago[deleted]
- Retric 9y agoIf you want to minimize the long distance walks add an exponential weight for distance then solve. There are many ways to go about this stuff, but the goal is to map your preferences to the weight function.
- modalduality 9y agoRight, but then the problem is no longer linear and approximating is more difficult. I'm not exactly sure what you mean by "exponential weight" in a linear program, do you have an example?
- Spivak 9y agoSo say you have a graph on distance, d, that you want to weight based on a preference, p, from 0-5 going from least preferred to most preferred. You might make your weight function as w(d, p) = d * (2 ^ p)
- modalduality 9y agoThat's fine, but `p` is a variable, not a constant, in the original post's case, right?
- Evelin789 9y agowhat Ralph answered I didnt know that anybody can get paid $6830 in 1 month on the > computer . i was reading this>>>>>>>>>>>http://ow.ly/iBXm30dNtIZ http://ow.ly/iBXm30dNtIZ
- tgb 9y agoThat doesn't seem necessary. Picking a value of p just selects how much you prefer short hope to shorter total distance.
- Retric 9y agoI am not sure what your asking? Your just assigning constants for weights on each trip a>b = K1, a>c = K2. I am saying you may map K1 as √((x1-x2)^2+(y1-y2)^2) to find least distance, but TSP allows for arbitrary constants. So remove the √ and long trips will be strongly avoided. PS: As far as I know you can use any arbitrary set of constants then use a linear solver. Or am I forgetting about something?