NP-hard problems have numerous applications in various fields such as networks,
computer systems, circuit design, etc. However, no efficient algorithms have
been found for NP-hard problems. It has been commonly believed that no efficient algorithms
for NP-hard problems exist, i.e., that P6=NP. Recently, it has been observed
that there are parameters much smaller than input sizes in many instances of NP-hard
problems in the real world. In the last twenty years, researchers have been interested
in developing efficient algorithms, i.e., fixed-parameter tractable algorithms, for those
instances with small parameters. Fixed-parameter tractable algorithms can practically
find exact solutions to problem instances with small parameters, though those
problems are considered intractable in traditional computational theory.
In this dissertation, we propose a new approach of algorithm design and analysis:
discovering better measures for problems. In particular we use two measures instead of
the traditional single measure?input size to design algorithms and analyze their time
complexity. For several classical NP-hard problems, we present improved algorithms
designed and analyzed with this new approach,
First we show that the new approach is extremely powerful for designing fixedparameter
tractable algorithms by presenting improved fixed-parameter tractable algorithms
for the 3D-matching and 3D-packing problems, the multiway cut problem, the feedback vertex set problems on both directed and undirected
graph and the max-leaf problems on both directed and undirected graphs. Most of
our algorithms are practical for problem instances with small parameters.
Moreover, we show that this new approach is also good for designing exact algorithms
(with no parameters) for NP-hard problems by presenting an improved exact
algorithm for the well-known satisfiability problem.
Our results demonstrate the power of this new approach to algorithm design and
analysis for NP-hard problems. In the end, we discuss possible future directions on
this new approach and other approaches to algorithm design and analysis.
| Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/ETD-TAMU-2009-08-7010 |
| Date | 2009 August 1900 |
| Creators | Liu, Yang |
| Contributors | Chen, Jianer |
| Source Sets | Texas A and M University |
| Language | en_US |
| Detected Language | English |
| Type | Book, Thesis, Electronic Dissertation, text |
| Format | application/pdf |
Page generated in 0.0022 seconds