• Login
    View Item 
    •   etd@IISc
    • Division of Electrical, Electronics, and Computer Science (EECS)
    • Computer Science and Automation (CSA)
    • View Item
    •   etd@IISc
    • Division of Electrical, Electronics, and Computer Science (EECS)
    • Computer Science and Automation (CSA)
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Recovery Algorithms for planted structures in Semi-random models

    View/Open
    Thesis full text (798.0Kb)
    Author
    Paul, Rameesh
    Metadata
    Show full item record
    Abstract
    For many NP-hard problems, the analysis of best-known approximation algorithms yields “poor” worst-case guarantees. However, using various heuristics, the problems can be solved (to some extent) in real-life instances. This success can be attributed to the atypicality of worst-case instances in real life, and therefore motivates studying the problem in “easier” instances. Analyzing the problem in Planted solution models and Semi-random models is one such systematic approach along these lines. In this thesis, we study planted solution models and semi-random models for various graph problems. Given a graph G with n vertices, we consider the task of finding the largest induced subgraph of G with a particular structure. We start by studying the problem where the particular structure is a planar graph. Next, we look at the Odd Cycle Transversal problem or equivalently the problem of finding the largest induced bipartite subgraph. Finally, we study the problem of finding the largest independent set in r-uniform hypergraphs. All these problems are NP-hard and have abysmal worst-case approximation guarantees. An instance of a planted solution model is constructed by starting with a set of vertices V, and choosing a set S ⊆ V of k vertices, and adding a particular structure to it. Edges between pairs of vertices in S x (V\S) and (V\S) x (V\S) are added independently with probability p. The algorithmic task then is to recover this planted structure. As a special case for all these problems, when the planted structure is an empty graph, the problem reduces to recovering a planted independent set and we dont expect recovery algorithms for k =o(√n). For the problem of finding the largest induced bipartite subgraph, we give an exact recovery algorithm that works for k = Ω_p(n log n)^1/2. For the problem of finding the maximum independent set in r-uniform hypergraphs, we give an algorithm that works for Ω_p(n^{r-1/r-0.5}). Our results also hold for a natural semi-random model of instances inspired by Feige and Kilian [FK01] model. Our algorithms are based on analyzing continuous relaxations of these problems. We employ techniques from Spectral Graph Theory, Convex Optimization (Linear Programs (LPs) and Semi-Definite Programs (SDPs) relaxations), and Lasserre/Sum-of-Squares hierarchy strengthening of convex relaxations.
    URI
    https://etd.iisc.ac.in/handle/2005/5819
    Collections
    • Computer Science and Automation (CSA) [392]

    etd@IISc is a joint service of SERC & J R D Tata Memorial (JRDTML) Library || Powered by DSpace software || DuraSpace
    Contact Us | Send Feedback | Thesis Templates
    Theme by 
    Atmire NV
     

     

    Browse

    All of etd@IIScCommunities & CollectionsTitlesAuthorsAdvisorsSubjectsBy Thesis Submission DateThis CollectionTitlesAuthorsAdvisorsSubjectsBy Thesis Submission Date

    My Account

    LoginRegister

    etd@IISc is a joint service of SERC & J R D Tata Memorial (JRDTML) Library || Powered by DSpace software || DuraSpace
    Contact Us | Send Feedback | Thesis Templates
    Theme by 
    Atmire NV