Trukhanov, Svyatoslav (2008-08). Novel approaches for solving large-scale optimization problems on graphs. Doctoral Dissertation. Thesis uri icon

abstract

  • This dissertation considers a class of closely related NP-hard otpimization problems on graphs that arise in many important applications, including network-based data mining, analysis of the stock market, social networks, coding theory, fault diagnosis, molecular biology, biochemistry and genomics. In particular, the problems of interest include the classical maximum independent set problem (MISP) and maximum clique problem (MCP), their vertex-weighted vesrions, as well as novel optimization models that can be viewed as practical relaxations of their classical counterparts. The concept of clique has been a popular instrument in analysis of networks, and is, essentially, an idealized model of a "closely connected group", or a cluster. But, at the same time, the restrictive nature of the definition of clique makes the clique model impractical in many applications. This motivated the development of clique relaxation models that relax different properties of a clique. On the one hand, while still possessing some clique-like properties, clique relaxations are not as "perfect" as cliques; and on the other hand, they do not exhibit the disadvantages associated with a clique. Using clique relaxations allows one to compromise between perfectness and flexibility, between ideality and reality, which is a usual issue that an engineer deals with when applying theoretical knowledge to solve practical problems in industry. The clique relaxation models studied in this dissertation were first proposed in the literature on social network analysis, however they have not been well investigated from a mathematical programming perspective. This dissertation considers new techniques for solving the MWISP and clique relaxation problems and investigates their effectiveness from theoretical and computational perspectives. The main results obtained in this work include (i) developing a scale-reduction approach for MWISP based on the concept of critical set and comparing it theoretically with other approaches; (ii) obtaining theoretical complexity results for clique relaxation problems; (iii) developing algorithms for solving the clique relaxation problems exactly; (iv) carrying out computational experiments to demonstrate the performance of the proposed approaches, and, finally, (v) applying the obtained theoretical results to several real-life problems.
  • This dissertation considers a class of closely related NP-hard otpimization problems
    on graphs that arise in many important applications, including network-based data
    mining, analysis of the stock market, social networks, coding theory, fault diagnosis,
    molecular biology, biochemistry and genomics. In particular, the problems of interest
    include the classical maximum independent set problem (MISP) and maximum clique
    problem (MCP), their vertex-weighted vesrions, as well as novel optimization models
    that can be viewed as practical relaxations of their classical counterparts.
    The concept of clique has been a popular instrument in analysis of networks, and
    is, essentially, an idealized model of a "closely connected group", or a cluster. But,
    at the same time, the restrictive nature of the definition of clique makes the clique
    model impractical in many applications. This motivated the development of clique
    relaxation models that relax different properties of a clique. On the one hand, while
    still possessing some clique-like properties, clique relaxations are not as "perfect" as
    cliques; and on the other hand, they do not exhibit the disadvantages associated with
    a clique. Using clique relaxations allows one to compromise between perfectness and
    flexibility, between ideality and reality, which is a usual issue that an engineer deals
    with when applying theoretical knowledge to solve practical problems in industry.
    The clique relaxation models studied in this dissertation were first proposed in the
    literature on social network analysis, however they have not been well investigated from a mathematical programming perspective.
    This dissertation considers new techniques for solving the MWISP and clique
    relaxation problems and investigates their effectiveness from theoretical and computational
    perspectives. The main results obtained in this work include (i) developing a
    scale-reduction approach for MWISP based on the concept of critical set and comparing
    it theoretically with other approaches; (ii) obtaining theoretical complexity results
    for clique relaxation problems; (iii) developing algorithms for solving the clique relaxation
    problems exactly; (iv) carrying out computational experiments to demonstrate
    the performance of the proposed approaches, and, finally, (v) applying the obtained
    theoretical results to several real-life problems.

publication date

  • August 2008