The Steiner tree problem is to nd a shortest subgraph
that spans a given set of vertices in a graph. This problem
is known to be NP-hard and it is well known that a polynomial time
2-approximation algorithm exists. In 1996 Zelikovsky [11] suggested
an approximation algorithm for the Steiner tree problem that is called
the relative greedy algorithm. Till today the performance ratio of this
algorithm is not known. Zelikovsky provided 1.694 as an upper bound
and Gröpl, Hougardy, Nierho and Prömel [6] proved that 1.333 is a
lower bound. In this paper we improve the lower bound for the performance
ratio of the relative greedy algorithm to 1.385.
In a database of about 2000 approved drugs, represented by 105 structural conformers,
we have performed 2D comparisons (Tanimoto coefficients) and 3D superpositions. For one class of drugs the correlation
between structural resemblance and similar action was analysed in detail.
In general Tanimoto cofficients and 3D scores give similar results, but we
find that 2D similarity measures neglect important structural/funtional
features. Examples for both over- and underestimation of similarity by
2D metrics are discussed. The required additional effort for 3D superpositions
is assessed by implementation of a fast algorithm with a processing
time below 0:01 seconds and a more sophisticated approach (0:5 seconds
per superposition). According to the improvement of similarity detection
compared to 2D screening and the pleasant rapidity on a desktop PC,
full{atom 3D superposition will be an upcoming method of choice for
library prioritization or similarity screening approaches.
The weighted matching problem is to find a matching in a weighted graph
that has maximum weight. The fastest known algorithm for this problem has running time
O(nm +n2 log n). Many real world problems require graphs of such large size that this running
time is too costly. We present a linear time approximation algorithm for the weighted
matching problem with a performance ratio of 2
3 ???? ". This improves the previously best
performance ratio of 1
2 .
Recently two different linear time approximation algorithms for the weighted matching problem in graphs have been suggested [5][17]. Both these algorithms have a performance ratio of 1/2. In this paper we present a set of local improvement operations and prove that it guarantees a performance ratio of 2/3. We show that a maximal set of these local improvements can be found in linear time.
To see how these local improvements behave in practice we conduct an experimental comparison of four different approximation algorithms for calculating maximum weight matchings in weighted graphs. One of these algorithms is the commonly used Greedy algorithm which achieves a performance ratio of 1/2 but has O(m log n) runtime. The other three algorithms all have linear runtime. Two of them are the above mentioned 1/2 approximation algorithms. The third algorithm may have an arbitrarily bad performance ratio but in practice produces reasonably good results. We compare the quality of the algorithms on a test set of weighted graphs and study the improvement achieved by our local improvement operations. We also do a comparison of the runtimes of all algorithms.
We present a linear time approximation algorithm with a performance ratio of 1/2 for finding a maximum weight matching in an arbitrary graph. Such a result is already known and is due to Preis [STACS'99, Lecture Notes in Comput. Sci., Vol. 1563, 1999, pp. 259–269]. Our algorithm uses a new approach which is much simpler than the one given by Preis and needs no amortized analysis for its running time.
Motivation: The Dictionary of Interfaces in Proteins (DIP) is a database collecting the 3D structure of interacting parts of proteins that are called patches. It serves as a repository, in which patches similar to given query patches can be found. The computation of the similarity of two patches is time consuming and traversing the entire DIP requires some hours. In this work we address the question of how the patches similar to a given query can be identified by scanning only a small part of DIP. The answer to this question requires the investigation of the distribution of the similarity of patches.
Results: The score values describing the similarity of two patches can roughly be divided into three ranges that correspond to different levels of spatial similarity. Interestingly, the two iso-score lines separating the three classes can be determined by two different approaches. Applying a concept of the theory of random graphs reveals significant structural properties of the data in DIP. These can be used to accelerate scanning the DIP for patches similar to a given query. Searches for very similar patches could be accelerated by a factor of more than 25. Patches with a medium similarity could be found 10 times faster than by brute-force search.
Approximation algorithms have so far mainly been studied for problems that are not known to have polynomial time algorithms for solving them exactly. Here we propose an approximation algorithm for the weighted matching problem in graphs which can be
solved in polynomial time. The weighted matching problem is to find a matching in an
edge weighted graph that has maximum weight. The first polynomial time algorithm for this problem was given by Edmonds in 1965. The fastest known algorithm for the weighted matching problem has a running time of O(nm + n2 log n). Many real world problems require graphs of such large size that this running time is too costly. Therefore there is considerable need for faster approximation algorithms for the weighted matching problem. We present a linear time approximation algorithm for the weighted matching problem with a performance ratio arbitrarily close to 2/3 . This improves the previously best performance ratio of 1/2. Our algorithm is not only of theoretical interest but because it is easy to implement and the constants involved are quite small it is also useful in practice.
The terminal Steiner tree problem is a special version of
the Steiner tree problem, where a Steiner minimum tree has to be found
in which all terminals are leaves. We prove that no polynomial time approximation
algorithm for the terminal Steiner tree problem can achieve
an approximation ratio less than (1 - o(1)) ln n unless NP has slightly superpolynomial
time algorithms. Moreover, we present a polynomial time
approximation algorithm for the metric version of this problem with a performance
ratio of 2 , where denotes the best known approximation ratio
for the Steiner tree problem. This improves the previously best known
approximation ratio for the metric terminal Steiner tree problem of +2.