View Item 
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of UU Student Theses RepositoryBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

        The k-Cycling Dinner problem, and its placement in the computational complexity zoo

        Thumbnail
        View/Open
        Niels Scholten 5967406.pdf (376.9Kb)
        Publication date
        2020
        Author
        Scholten, N.C.
        Metadata
        Show full item record
        Summary
        In this paper, I introduce a new family of scheduling and routing problems. These problems are called the k-cycling dinner problems. Given a graph, the problem is to find a set of tuples of nodes for which the distance between these nodes is minimized under the following three constraints. Each node is present in exactly k tuples. Each pair of tuples is not allowed to share more than one node, and each node should have the same position within the tuple in all the tuples in which that node in present. I provide a constraint satisfaction program which is able to solve these problem, however this solution is not sufficiently fast. After explaining the necessary terms on Np-Completeness, I provide an NP-Completeness reduction proof for the 2-Cycling Dinner problem, which proves that the 2-Cycling Dinner problem is in the complexity class NP-Complete. This suggests that finding a solution to this problem would be very hard to do in polynomial time. This paper also contains an attempt to provide an NP-Completeness reduction proof for the 3-CD problem. These proofs offer strong arguments for researchers trying to solve these problems, to utilize approximation algorithms.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/38939
        Collections
        • Theses
        Utrecht university logo