Does a mathematical modelling on Christofides algorithm exist, is it even possible to create one?

  • $\begingroup$ What is the "distribution problem" you are trying to solve? $\endgroup$ – Curtis F Dec 8 '18 at 19:45
  • 1
    $\begingroup$ Your question makes little sense I'm afraid. TSP is a problem with a precise input and output. You can say things like "I have a problem in which I need to distribute items to locations, and this problem can be modeled as an instance of TSP". But what is your question exactly? $\endgroup$ – Juho Dec 8 '18 at 19:49
  • 1
    $\begingroup$ What do you mean by "a mathematical modelling on Christofides algorithm"? The algorithm has been analyzed mathematically: that's how we know that it works and know how long it takes. $\endgroup$ – David Richerby Dec 8 '18 at 22:08
  • $\begingroup$ @SebastianNielsen Um. Christofides's original paper? Are you proposing that he just said, "Hey, here's this algorithm. I dunno if it works or anything, but you guys might find it interesting"? Wikipedia? $\endgroup$ – David Richerby Dec 8 '18 at 22:17
  • $\begingroup$ @SebastianNielsen What do you mean by "a mathematical modelling"? $\endgroup$ – David Richerby Dec 8 '18 at 22:24

The mathematical model relevant for understanding Christofides' algorithm is not the algorithm itself but rather the problem it is trying to solving – the traveling salesman problem. This is a model for optimization problems which occur in practice.

Christofides' algorithm itself could also perhaps be considered a model, if it is supposed to represent the way that humans (or animals, or nature) solve the traveling salesman problem. But in fact, it doesn't – it was designed as an efficient algorithm for computers.

| cite | improve this answer | |
  • $\begingroup$ No. What I’m saying is more like that 7 isn’t a color. $\endgroup$ – Yuval Filmus Dec 9 '18 at 9:01
  • $\begingroup$ I think that’s the root of the problem. You seem to be trying to answer a questionable quiz question. Christofides’ algorithm is an algorithm or heuristic, not a model. It’s a category error to ask if it’s a mathematical model (though not completely out of the question, as I tried to explain in my answer). I don’t think your knowledge of mathematical modeling will be furthered by trying to answer nonsensical questions like this. $\endgroup$ – Yuval Filmus Dec 9 '18 at 9:12
  • $\begingroup$ How about asking your TA or professor? $\endgroup$ – Yuval Filmus Dec 9 '18 at 9:18
  • $\begingroup$ Complain to the dean. Unfortunately we cannot fix your university on this online platform. $\endgroup$ – Yuval Filmus Dec 9 '18 at 9:24
  • $\begingroup$ In that case, your parents should contact the principal. We can’t fix the high school system online. $\endgroup$ – Yuval Filmus Dec 9 '18 at 9:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.