taivop / eth-algolab

Algorithms Lab
https://moodle-app2.let.ethz.ch/course/view.php?id=1614
2 stars 1 forks source link

2: Boats #8

Open taivop opened 9 years ago

taivop commented 9 years ago

https://moodle-app2.let.ethz.ch/pluginfile.php/159272/mod_resource/content/1/boats.pdf

taivop commented 9 years ago

Greedy prolly works, but with which local optimality measure?

taivop commented 9 years ago

Approach: consider each positioning of a boat separately, i.e. we choose between combinations of (boat, position relative to its ring). This way the problem is actually reduced to the interval scheduling problem shown in class.