Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
The Ferry Cover Problem
National Technical University of Athens.
2007 (English)In: Fun with Algorithms, Proceedings / [ed] Crescenzi, P; Prencipe, G; Pucci, G, Springer Berlin/Heidelberg, 2007, 227-239 p.Conference paper, Published paper (Refereed)
Abstract [en]

In the classical wolf-goat-cabbage puzzle, a ferry boat man must ferry three items across a river using a boat that has room for only one, without leaving two incompatible items on the same bank alone. In this paper we define and study a family of optimization problems called FERRY problems, which may be viewed as generalizations of this familiar puzzle. In all FERRY problems we are given a set of items and a graph with edges connecting items that must not be left together unattended. We present the FERRY COVER problem (FC), where the objective is to determine the minimum required boat size and demonstrate a close connection with VERTEX COVER which leads to hardness and approximation results. We also completely solve the problem on trees. Then we focus on a variation of the same problem with the added constraint that only I round-trip is allowed (FC1). We present a reduction from MAX-NAE-{3}-SAT which shows that this problem is NP-hard and APX-hard. We also provide an approximation algorithm for trees with a factor asymptotically equal to 4/3. Finally, we generalize the above problem to define FC, where at most m round-trips are allowed, and MFTk, which is the problem of minimizing the number of round-trips when the boat capacity is k. We present some preliminary lemmata for both, which provide bounds on the value of the optimal solution, and relate them to FC.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2007. 227-239 p.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 4475
Keyword [en]
approximation algorithms, graph algorithms, vertex cover, transportation problems, wolf-goat-cabbage puzzle
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-58593ISI: 000247837500020ISBN: 978-3-540-72913-6 (print)OAI: oai:DiVA.org:kth-58593DiVA: diva2:473394
Conference
4th International Conference on Fun with Algorithms, FUN 2007; Castiglioncello; 3 June 2007 through 5 June 2007
Note
QC 20120109Available from: 2012-01-05 Created: 2012-01-05 Last updated: 2012-01-09Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Lampis, Michael
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 26 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf