Traveling Salesman Problem

[Memorice]

Ik verdiep me momenteel in het Traveling Salesman Problem en het is mij niet helemaal duidelijk wat het verschil tussen de volgende termen is:

'constant performance ratio' en 'performance ratio bounded by a constant'

Is er iemand die dit toevallig weet? Google levert namelijk niet heel veel resultaat.

[Janoz]

Om daar een goede uitspraak over te doen is het handig wanneer je ook de context verteld. Kun je niet de alinea overnemen waarin deze termen gebruikt worden?

Uitgaande van alleen deze uitspraken vermoed ik dat met de eerste wordt bedoeld dat de performance altijd hetzelfde is. Het best case scenario is gelijk aan het worstcase scenario.

Het 'bounded by a constant' vind ik lastiger. Aan de ene kant kunnen ze daarmee bedoelen dat het bestcase scenario een lower boundary heeft, maar het zou ook kunnen betekenen dat de worstcase een upper boundary heeft.

Bij beide van deze verklaringen ben ik er van uit gegaan dat ze met 'ratio' de relative performance van een algorithme bedoelen tov de grootte van de input, ook wel bekend als de big O notation.

[Memorice]

Eigenlijk zijn het twee vragen van een universitair vak, waarbij de ene vraag eindigt met:

Give an approximation algorithm that runs in polynomial time and has a performance ratio bounded by a constant.

En de andere vraag is:

Consider the traveling salesman problem with instances that are not symmetric but still fulfil the triangle inequality. Is there a polynomial time approximation algorithm with constant performance ratio?

Ik ben er overigens van op de hoogte dat de laatste vraag nog steeds een open vraag is in de wetenschap...

edit: Overigens kan het volgens mij ook betrekking hebben op hoe goed de oplossing van een algoritme is met betrekking tot de best mogelijke oplossing. Bijvoorbeeld Christofides’s algorithm benaderd de optimale oplossing met een ratio van 3/2.

[ Voor 19% gewijzigd door Memorice op 23-02-2009 21:57 ]

[EfBe]

MEMORICE schreef op maandag 23 februari 2009 @ 21:54:
Eigenlijk zijn het twee vragen van een universitair vak, waarbij de ene vraag eindigt met:

Give an approximation algorithm that runs in polynomial time and has a performance ratio bounded by a constant.

Lijkt me raar aangezien travelers salesman een NP-Hard probleem is. Er is wel een rus geweest laatst die een paper heeft geschreven omtrent een polynomial algorithme, maar dat is een algorithme dat daarna niet voor 100% waterdicht bleek. Ik snap dus niet echt hoe deze vraag ooit beantwoord kan worden.

Of gaat deze vraag niet over het travelers salesman problem?

En de andere vraag is:

Consider the traveling salesman problem with instances that are not symmetric but still fulfil the triangle inequality. Is there a polynomial time approximation algorithm with constant performance ratio?

Ik ben er overigens van op de hoogte dat de laatste vraag nog steeds een open vraag is in de wetenschap...

edit: Overigens kan het volgens mij ook betrekking hebben op hoe goed de oplossing van een algoritme is met betrekking tot de best mogelijke oplossing. Bijvoorbeeld Christofides’s algorithm benaderd de optimale oplossing met een ratio van 3/2.

Zie vorige antwoord.

[Nick The Heazk]

EfBe schreef op dinsdag 24 februari 2009 @ 09:24:
Lijkt me raar aangezien travelers salesman een NP-Hard probleem is.

Dat een probleem NP-Hard is sluit niet uit dat er approximatie-algoritmen zijn die een tijdscomplexiteit hebben die bijvoorbeeld polynomiaal is.

MEMORICE schreef op maandag 23 februari 2009 @ 21:41:
Ik verdiep me momenteel in het Traveling Salesman Problem en het is mij niet helemaal duidelijk wat het verschil tussen de volgende termen is:

'constant performance ratio' en 'performance ratio bounded by a constant'

Het lijkt me in deze context gewoon te gaan om twee dezelfde termen. In beide gevallen (in de twee vragen) worden deze termen gebruikt om aan te geven wat de maximale afwijking van het approximatie-algoritme is ten opzichte van de exacte oplossing van TSP. Dit wil dus zeggen dat oplossingen bepaalt door het algoritme van Christofides maximaal 1,5 keer langer zijn dan de echte oplossing van het TSP probleem.

MEMORICE schreef op maandag 23 februari 2009 @ 21:54:
Consider the traveling salesman problem with instances that are not symmetric but still fulfil the triangle inequality. Is there a polynomial time approximation algorithm with constant performance ratio?

Ik ben er overigens van op de hoogte dat de laatste vraag nog steeds een open vraag is in de wetenschap...

Ik ben er niet zeker van dat dit een openstaande vraag is (tenzij mijn interpretatie van constant performance ratio verkeerd is). Je kunt voor dit soort TSP problemen een vrij eenvoudig algoritme ontwerpen met een tijdscomplexiteit die kwadratisch is in het aantal knopen. Ik geef een hint: minimum spanning trees.

[Memorice]

Ik ken de algoritmes mbt minimum spanning trees, maar gezien de docent bij de tweede vraag aangegeven heeft dat het nog steeds een openstaande vraag is in de wetenschap, terwijl de eerste vraag dat volgens de docent niet is. Lijkt het mij dat er verschil moet zijn tussen beide termen, omdat anders beide vragen equivalent aan elkaar zijn. De opgaven zijn overigens al ingeleverd, dus ik zal het over twee weken eens aan de docent vragen (deze zie ik niet eerder).

[EfBe]

Ik heb even de paper opgezocht:
http://arxiv.org/abs/cs/0610042