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.
| Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/ETD-TAMU-2986 |
| Date | 15 May 2009 |
| Creators | Trukhanov, Svyatoslav |
| Contributors | Butenko, Sergiy I. |
| Source Sets | Texas A and M University |
| Language | en_US |
| Detected Language | English |
| Type | Book, Thesis, Electronic Dissertation, text |
| Format | electronic, application/pdf, born digital |
Page generated in 0.0012 seconds