排序方式: 共有10条查询结果,搜索用时 15 毫秒
1
1.
In this study, we investigated the basis of the resistance of muscles to tumor metastases. We found that a low molecular weight fraction (Mr <3000) of skeletal muscle cell-conditioned medium (MCM) markedly inhibits the proliferation of carcinoma, sarcoma, or melanoma cell lines in vitro. The MCM exerts a cytostatic effect on tumor cell growth and arrests the cells in G0/G1 of the cell cycle. However, normal cell proliferation of cells such as bone marrow cells or fibroblasts was found to be refractory to the influence of the MCM. A reduction in melanoma growth was observed in mice treated with the MCM. Adenosine was identified as one of the active components in the MCM by using high-performance liquid chromatography separations, mass spectra, and nuclear magnetic resonance analyses. At a concentration of 4 microM, equal to that found in the MCM, adenosine inhibits the proliferation of tumor cell lines (Nb2 lymphoma, K-562 leukemia, and LNCaP prostate carcinoma cells) while stimulating the proliferation of normal murine bone marrow cells. By similar methods, additional inhibitory components were detected in the MCM in a molecular mass range of 600-800 Da. The ability of adenosine and other low molecular weight components to specifically inhibit tumor cell growth in vitro and in vivo may account for the resistance of muscle to tumor metastases. 相似文献
2.
R. Bar-Yehuda 《Algorithmica》2000,27(2):131-144
We present a simple and unified approach for developing and analyzing approximation algorithms for covering problems. We
illustrate this on approximation algorithms for the following problems: Vertex Cover, Set Cover, Feedback Vertex Set, Generalized
Steiner Forest, and related problems.
The main idea can be phrased as follows: iteratively, pay two dollars (at most) to reduce the total optimum by one dollar
(at least), so the rate of payment is no more than twice the rate of the optimum reduction. This implies a total payment (i.e.,
approximation cost) ≤ twice the optimum cost.
Our main contribution is based on a formal definition for covering problems, which includes all the above fundamental problems
and others. We further extend the Bafna et al. extension of the Local-Ratio theorem. Our extension eventually yields a short
generic r -approximation algorithm which can generate most known approximation algorithms for most covering problems.
Another extension of the Local-Ratio theorem to randomized algorithms gives a simple proof of Pitt's randomized approximation
for Vertex Cover. Using this approach, we develop a modified greedy algorithm, which for Vertex Cover gives an expected performance
ratio ≤ 2 .
Received September 17, 1997; revised March 5, 1998. 相似文献
3.
Bar-Yehuda R. Chor B. Kushilevitz E. Orlitsky A. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》1993,39(6):1930-1943
Two parties, each holding one input of a two-variable function, communicate in order to determine the value of the function. Each party wants to expose as little of its input as possible to the other party. The authors prove tight bounds on the minimum amount of information about the individual inputs that must be revealed in the computation of most functions and of some specific ones. They also show that a computation that reveals little information about the individual inputs may require many more message exchanges than a more revealing computation 相似文献
4.
We solve some problems related toray shooting in the plane, such as finding the first object hit by a query ray or counting the number of objects intersected by the query line. Our main results are an algorithm for finding the first hit when the objects are lines, and an algorithm for the case when the objects are segments. If the segments form simple polygons, this information can be used for reducing the complexity of the algorithms. The algorithms are efficient in space and in query time. Moreover, they are simple and therefore of practical use.This research was partially supported by the NY Metropolitan Research Fund. The second author is currently at IBM Haifa Research Group, Haifa 32000, Israel. 相似文献
5.
We study the set-cover problem, i.e. given a collection C of subsets of a finite set U, find a minimum size subset C′⊆C such that every element in U belongs to at least one member of C. An instance (C,U) of the set-cover problem is k-bounded if the number of occurrences in C of any element is bounded by a constant k?2.We present an approximation algorithm for the k-bounded set-cover problem, that achieves the ratio , where ε is defined as . If ε is relatively high, we say that the problem is dense, and this ratio in this case is better than k, which is the best known constant ratio for this problem. In the case that the number of occurrences in C of any element is exactly k=2 the problem is known as the vertex-cover problem. For dense graphs, our algorithm achieves an approximation ratio better than that of Nagamochi and Ibaraki (Japan J. Indust. Appl. Math. 16 (1999) 369), and the same approximation ratios as Karpinski and Zelikovsky (Proceedings of DIMACS Workshop on Network Design: Connectivity and Facilities Location, Vol. 40, Princeton, 1998, pp. 169-178). In our algorithm we use a combinatorial property of the set-cover problem, which is based on the classical greedy algorithm for the set-cover problem. We use this property to define a “greedy-sequence”, which is defined over a given instance of the set-cover problem and its cover.In addition, we show evidence that the ratio we achieve for the ε-dense k-bounded set-cover problem is the best constant ratio one can expect. We do this by showing that finding a better constant ratio is as hard as finding a constant ratio better than k for the k-bounded set-cover problem in which the optimal cover is known to be of size at least . (k is the best known constant ratio for this version of the k-bounded set-cover problem.) We show a similar lower bound for the approximation ratio for the vertex-cover problem in ε-dense graphs. 相似文献
6.
We study the bandwidth allocation problem (bap) in bounded degree trees. In this problem we are given a tree and a set of connection requests. Each request consists of
a path in the tree, a bandwidth requirement, and a weight. Our goal is to find a maximum weight subset S of requests such that, for every edge e, the total bandwidth of requests in S whose path contains e is at most 1. We also consider the storage allocation problem (sap), in which it is also required that every request in the solution is given the same contiguous portion of the resource in
every edge in its path. We present a deterministic approximation algorithm for bap in bounded degree trees with ratio
. Our algorithm is based on a novel application of the local ratio technique in which the available bandwidth is divided into narrow strips and requests with very small bandwidths are allocated in these
strips. We also present a randomized (2+ε)-approximation algorithm for bap in bounded degree trees. The best previously known ratio for bap in general trees is 5. We present a reduction from sap to bap that works for instances where the tree is a line and the bandwidths are very small. It follows that there exists a deterministic
2.582-approximation algorithm and a randomized (2+ε)-approximation algorithm for sap in the line. The best previously known ratio for this problem is 7.
A preliminary version of this paper was presented at the 14th Annual European Symposium on Algorithms (ESA), 2006. 相似文献
7.
8.
A pair (T,C) of a tree T and a coloring C is called a colored tree. Given a colored tree (T,C) any coloring C′ of T is called a recoloring of T. Given a weight function on the vertices of the tree the recoloring distance of a recoloring is the total weight of recolored vertices. A coloring of a tree is convex if for any two vertices u and v that are colored by the same color c, every vertex on the path from u to v is also colored by c. In the minimum convex recoloring problem we are given a colored tree and a weight function and our goal is to find a convex recoloring of minimum recoloring distance.
The minimum convex recoloring problem naturally arises in the context of phylogenetic trees. Given a set of related species the goal of phylogenetic reconstruction is to construct a tree that would best describe the
evolution of this set of species. In this context a convex coloring corresponds to perfect phylogeny. Since perfect phylogeny is not always possible the next best thing is to find a tree which is as close to convex as possible,
or, in other words, a tree with minimum recoloring distance.
We present a (2+ε)-approximation algorithm for the minimum convex recoloring problem, whose running time is O(n
2+n(1/ε)241/ε
). This result improves the previously known 3-approximation algorithm for this NP-hard problem. We also present an algorithm
for computing an optimal convex recoloring whose running time is
, where n
* is the number of colors that violate convexity in the input tree, and Δ is the maximum degree of vertices in the tree. The
parameterized complexity of this algorithm is O(n
2+n⋅k⋅2
k
). 相似文献
9.
Summary This paper presents an efficient randomized emulation ofsingle-hop radio networkwith collision detection onmulti-hop radio networkwithout collision detection. Each step of the single-hop network is emulated by
rounds of the multi-hop network and succeeds with probability 1–. (n is the number of processors,D the diameter and the maximum degree). It is shown how to emulate any polynomial algorithm such that the probability of failure remains . A consequence of the emulation is an efficient randomized algorithm for choosing a leader in a multi-hop network.
Reuven Bar-Yehuda was born in Iran, on July 17th 1951. Received B.A., M.Sc., and D.Sc. in Computer Science from the Technion — Israel Institute of Technology, Haifa, Israel, in 1978, 1980, and 1983, respectively. He is currently a Senior Lecturer of Computer Science at the Technion. From 1984 to 1986, he was a visiting assistant professor in the Computer Science Dept. at the Duke Univesity His research interests include computational geometry, VLSI, graph algorithms and distributed algorithms.
Oded Goldreich was born in Tel-Aviv, Israel, on February 4th 1957. Received B.A., M.Sc., and D.Sc. in Computer Science from the Technion — Israel Institute of Technology, Haifa, Israel, in 1980, 1982, and 1983, respectively. He is currently an Associate Professor of Computer Science at the Technion. From 1983 to 1986, he was a postdoctoral fellow at MIT's Laboratory for Computer Science. His research interests include cryptography and related areas, relation between randomness and algorithms, and distributed computation.
Alon Itai was born in Scotland, on December 12th 1946. Received B.Sc. in Mathematics from the Hebrew University in Jerusalem in 1969. M.Sc., and Ph.D. in Computer Science from the Weizmann Institute of Science, Rehovot, Israel in 1971 and 1976. He is currently an Associate Professor of Computer Science at the Technion. His research interests include randomized and distributed algorithms, computational learning theory and performance evaluation.The second author was partially supported by grant No. 86-00301 from the United States—Israel Bi-national Science Foundation BSF), Jerusalem, Israel. 相似文献
10.
Given a bounded integer program with n variables and m constraints, each with two variables, we present an O(mU) time and O(m) space feasibility algorithm, where U is the maximal variable range size. We show that with the same complexity we can find an optimal solution for the positively
weighted minimization problem for monotone systems. Using the local-ratio technique we develop an O(nmU) time and O(m) space 2 -approximation algorithm for the positively weighted minimization problem for the general case. We further generalize all
results to nonlinear constraints (called axis-convex constraints ) and to nonlinear (but monotone) weight functions.
Our algorithms are not only better in complexity than other known algorithms, but also considerably simpler, and they contribute
to the understanding of these very fundamental problems.
Received June 21, 1996; revised December 5, 1997. 相似文献
1