Spelling suggestions: "subject:"parameterization computational""
1 |
Parameterized algorithms and computational lower bounds: a structural approachXia, Ge 30 October 2006 (has links)
Many problems of practical significance are known to be NP-hard, and hence, are unlikely
to be solved by polynomial-time algorithms. There are several ways to cope with
the NP-hardness of a certain problem. The most popular approaches include heuristic
algorithms, approximation algorithms, and randomized algorithms. Recently, parameterized
computation and complexity have been receiving a lot of attention. By
taking advantage of small or moderate parameter values, parameterized algorithms
provide new venues for practically solving problems that are theoretically intractable.
In this dissertation, we design efficient parameterized algorithms for several wellknown
NP-hard problems and prove strong lower bounds for some others. In doing
so, we place emphasis on the development of new techniques that take advantage of
the structural properties of the problems.
We present a simple parameterized algorithm for Vertex Cover that uses polynomial
space and runs in time O(1.2738k + kn). It improves both the previous
O(1.286k + kn)-time polynomial-space algorithm by Chen, Kanj, and Jia, and the
very recent O(1.2745kk4 + kn)-time exponential-space algorithm, by Chandran and
Grandoni. This algorithm stands out for both its performance and its simplicity. Essential
to the design of this algorithm are several new techniques that use structural
information of the underlying graph to bound the search space.
For Vertex Cover on graphs with degree bounded by three, we present a still better algorithm that runs in time O(1.194k + kn), based on an âÂÂalmost-globalâÂÂ
analysis of the search tree.
We also show that an important structural property of the underlying graphs âÂÂ
the graph genus â largely dictates the computational complexity of some important
graph problems including Vertex Cover, Independent Set and Dominating Set.
We present a set of new techniques that allows us to prove almost tight computational
lower bounds for some NP-hard problems, such as Clique, Dominating Set,
Hitting Set, Set Cover, and Independent Set. The techniques are further extended
to derive computational lower bounds on polynomial time approximation schemes for
certain NP-hard problems. Our results illustrate a new approach to proving strong
computational lower bounds for some NP-hard problems under reasonable conditions.
|
2 |
Effective algorithms and protocols for wireless networking: a topological approachZhang, Fenghui 10 October 2008 (has links)
Much research has been done on wireless sensor networks. However, most protocols
and algorithms for such networks are based on the ideal model Unit Disk Graph
(UDG) model or do not assume any model. Furthermore, many results assume the
knowledge of location information of the network. In practice, sensor networks often
deviate from the UDG model significantly. It is not uncommon to observe stable long
links that are more than five times longer than unstable short links in real wireless
networks. A more general network model, the quasi unit-disk graph (quasi-UDG)
model, captures much better the characteristics of wireless networks. However, the
understanding of the properties of general quasi-UDGs has been very limited, which
is impeding the design of key network protocols and algorithms.
In this dissertation we study the properties for general wireless sensor networks
and develop new topological/geometrical techniques for wireless sensor networking.
We assume neither the ideal UDG model nor the location information of the nodes.
Instead we work on the more general quasi-UDG model and focus on figuring out
the relationship between the geometrical properties and the topological properties of
wireless sensor networks. Based on such relationships we develop algorithms that can
compute useful substructures (planar subnetworks, boundaries, etc.). We also present direct applications of the properties and substructures we constructed including routing,
data storage, topology discovery, etc.
We prove that wireless networks based on quasi-UDG model exhibit nice properties
like separabilities, existences of constant stretch backbones, etc. We develop
efficient algorithms that can obtain relatively dense planar subnetworks for wireless
sensor networks. We also present efficient routing protocols and balanced data storage
scheme that supports ranged queries.
We present algorithmic results that can also be applied to other fields (e.g., information
management). Based on divide and conquer and improved color coding
technique, we develop algorithms for path, matching and packing problem that significantly
improve previous best algorithms. We prove that it is unlikely for certain
problems in operation science and information management to have any relatively
effective algorithm or approximation algorithm for them.
|
Page generated in 0.1348 seconds