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

        A Framework for Studying the Complexity of General ε-Robust Problems

        Thumbnail
        View/Open
        Masters_Thesis_Lammert_Westerdijk.pdf (1.307Mb)
        Publication date
        2024
        Author
        Westerdijk, Lammert
        Metadata
        Show full item record
        Summary
        We study a class of robust versions of ∃R-complete problems, parametrized by the robustness ε as part of the problem statement. By including ε in the problem statement and not the input, for some values of ε the problem can actually become easier than the original non-robust problem. Based on results for ε-Rudi, a robust version of unit disk intersection graph recognition, we derive a general framework for a wide family of ε-robust problems. The framework gives conditions on ε under which the ε-robust problem becomes polynomial-time solvable, or remains in ∃R, or admits a polynomially sized witness, or even becomes undecidable. Specifically, sufficient conditions on ε are given, independent of the specific problem, under which the ε-robust problem is in NP. In particular, ε should be polynomial-time computable and badly approximable by all real algebraic numbers. We begin with a detailed study of such badly approximable numbers, including a comparision with other results on approximation such as in diophantine approximation. We present an example of a computable, badly approximable number and conjecture that a polynomial-time computable, badly approximable number exists. We also present two example framework applications on robust versions of Packing and the Art Gallery Problem.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/48250
        Collections
        • Theses
        Utrecht university logo