Adenosine and other low molecular weight factors released by muscle cells inhibit tumor cell growth

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.     

One for the Price of Two: a Unified Approach for Approximating Covering Problems

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.     

Privacy, additional information and communication

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     

Variations on ray shooting

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.     

Approximating the dense set-cover problem

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.     

Resource Allocation in Bounded Degree Trees

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.     

Improved Approximation Algorithm for Convex Recoloring of Trees

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 ²+n(1/ε)²4^1/ε ). 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 ²+n⋅k⋅2 ^k ).     

Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detection

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.     

Efficient Algorithms for Integer Programs with Two Variables per Constraint<Superscript><Emphasis Type="Italic">1</Emphasis></Superscript>

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.