Search

We study the asymptotic expected behavior of the First Fit and First Fit Decreasing bin packing algorithms applied to items chosen uniformly from the interval (0,u], u ≤ 1. Our results indicate that the algorithms perform even better than previously expected.

We show that the STEINER TREE problem and TRAVELING SALESMAN problem for points in the plane are NP-complete when distances are measured either by the rectilinear (Manhattan) metric or by a natural discretized version of the Euclidean metric. Our proofs also indicate that the problems are NP-hard if the distance measure is the (unmodified) Euclidean metric. However, for reasons we discuss, there is some question as to whether these problems, or even the well-solved MINIMUM SPANNING TREE problem, are in NP when the distance measure is the Euclidean metric.

Bin packing problems, in which one is asked to pack items of various sizes into bins so as to optimize some given objective function, arise in a wide variety of contexts and have been studied extensively during the past ten years, primarily with the goal of finding fast “approximation algorithms” that construct near-optimal packings. Beginning with the classical one-dimensional bin packing problem first studied in the early 1970’s, we survey the approximation results that have been obtained for this problem and its many variants and generalizations, including recent (unpublished) work that reflects the currently most active areas of bin packing research. Our emphasis is on the worst-case performance guarantees that have been proved, but we also discuss work that has been done on expected performance and behavior “in practice,” as well as mentioning some of the many applications of these problems.

Publisher Summary This chapter summarizes a “good” graph coloring algorithms by the following two statements: (1) all the known graph coloring algorithms are “horrible”. (Algorithms that find the minimum number of colors take exponential time; algorithms which run in polynomial bounded time can find colorings which use a number of colors which is an arbitrary multiple of the optimum value) and (2) all the unknown graph coloring algorithms are probably not much better. (The general problem of finding a minimum coloring is NP-complete, and the problem of finding a coloring which uses fewer than twice the minimum number of colors is just as hard).

Using ultrafiltration, the successful removal of endogenous pyrogens from a complex glycoprotein (molecular wieght = 59,000) has been achieved. Several lots of lyophilized human chorionic gonadotropin were pyrogenic, according to the official USP Rabbit Pyrogen Test. Subsequent filtration using a 100,000 nominal molecular weight limit membrane removed a significant amount of the endogenous pyrogenic material. Molecular filtrates showed an average rise of 0.27°C in rabbits, whereas original samples showed an average rise of 1.01°C. A weighed amount of the raw lyophilized hormone was dissolved in sterile pyrogen-free 0.9% saline to yield an estimated biological activity of 500 USP units per milliliter. The activity of the hormone was determined by the official USP Test, using female weanling (22–23 days old) Wistar rats. Nearly 70% of the original activity was recovered in the filtrate. Appropriate experiments were run before the human chorionic gonadotropin solution was processed. For negative controls, the entire filtration system was initially flushed with six liters of hot (180°C) Water for Injection and then subsequently rinsed with same volume of pyrogen-free 0.9% saline. Solution modifications in ionic strength and pH, using a constant volume molecular wash of the retentate volumes, may improve recoveries of the original hormone activity.

We consider a problem of scheduling file transfers in a network so as to minimize overall finishing time, which we formalize as a problem of scheduling the edges of a weighted multigraph. Although the general problem is NP-complete, we identify polynomial time solvable special eases and derive good performance bounds for several natural approximation algorithms. The above results assume the existence of a central controller, but we also show how the approximation algorithms, along with their performance guarantees, can be adapted to a distributed regime.

The m -chromatic number Xm(G) of a graph G = (V, E) is the least integer k such that there exists a mapping f : V → {S ⊆ c {1,2,…, k} : |S| = m} having the property that f (u) f∩f(u) = Θ whenever {u,v } E E. This is a generalization of the standard notion of chromatic number and arises in connection with mobile telephone frequency assignments. Answering a question of Lovasz, our first result shows that for any m≥ 1 any any E +1 (G)/,Xm,(G) mo , for which X mo (G)/mo= lim m Xm,(G)/m , can be asymptotically as large as e √(nlog n)/2 for some n vertex graphs, though it can never exceed e (n logn)/2 .

This paper updates a survey [53] written about 3 years ago. All of the results mentioned there are covered here as well. However, as a major justification for this second edition we shall be presenting many new results, some of which represent important advances. As a measure of the impressive amount of research in just 3 years, the present reference list more than doubles the list in [53].

T. Parsons originally proposed and studied the following pursuit-evasion problem on graphs: Members of a team of searchers traverse the edges of a graph G in pursuit of a fugitive, who moves along the edges of the graph with complete knowledge of the locations of the pursuers. What is the smallest number s ( G ) of searchers that will suffice for guaranteeing capture of the fugitive? It is shown that determining whether s ( G ) ≤ K , for a given integer K , is NP-complete for general graphs but can be solved in linear time for trees. We also provide a structural characterization of those graphs G with s ( G ) ≤ K for K = 1, 2, 3.

Publisher Summary This chapter focuses on the ω-conotoxins and their receptor targets. ω-conotoxins show remarkable tissue specificity, at least in comparison with other presently known Ca channel blockers, including the dihydropyridines. Thus, at the present time ω-conotoxins are known to target only voltage-sensitive Ca channels in neuronal tissue but not Ca channels in skeletal muscle, smooth muscle, or cardiac muscle. However, within vertebrate neuronal tissue, the chapter presents evidence that the ω-conotoxins have multiple receptor subtypes. The results of these studies suggest that, at presynaptic termini, there may well be several different voltage-sensitive Ca channel subtypes.

Many excellent papers 1-9 have been written recently concerning the type and amount of surgery to be done for the more perfect correction of intermittent exotropia. To satisfy my own curiosity and to add further clarity to this field, I reviewed 451 consecutive cases of exotropia done on the ward service of the Massachusetts Eye and Ear Infirmary. These included: (1) overcorrected esotropias, (2) constant exotropias, (3) alternating exotropias, (4) exotropias which have as their basis reduced vision and resultant deviation, and (5) intermittent exotropias with ( a ) convergence insufficiency and ( b ) divergence excess. Only in this last category was it possible to find any definite relationship between type and amount of surgery and the degree of stereopsis. Method of Selection of Cases In Category 5, intermittent exotropia, I have used Costenbader's classification 3 for delineating divergence excess, and only this will be covered in this paper. The characteristics for divergence

Whether an ophthalmologist prefers a broad basal iridectomy (keyhole) or the peripheral iridectomy or iridectomies (round-pupil) depends in a large part upon where he is practicing and where he received his training. However, a keyhole iridectomy is usually the choice in eyes where an old uveitis exists or in those cases where pupillary dilatation is poor. There is another category in which a broad basal iridectomy is considered essential by some ophthalmologists. That is, in cases where the first eye developed a retinal detachment or pupillary block glaucoma from vitreous herniation. The reasons for maintaining the round pupil are, as we all know, as follows: There is a more perfect optical system, said by some to be more physiologic, with resulting (a) less glare, (b) less astigmatism, (c) better depth of field. It is cosmetically more pleasing. There is less chance of vitreous loss. There is more effective use of

It is widely believed that showing a problem to be NP-complete is tantamount to proving its computational intractability. In this paper we show that a number of NP-complete problems remain NP-complete even when their domains are substantially restricted. First we show the completeness of SIMPLE MAX CUT (MAX CUT with edge weights restricted to value 1), and, as a corollary, the completeness of the OPTIMAL LINEAR ARRANGEMENT problem. We then show that even if the domains of the NODE COVER and DIRECTED HAMILTONIAN PATH problems are restricted to planar graphs, the two problems remain NP-complete, and that these and other graph problems remain NP-complete even when their domains are restricted to graphs with low node degrees. For GRAPH 3-COLORABILITY, NODE COVER, and UNDIRECTED HAMILTONIAN CIRCUIT, we determine essentially the lowest possible upper bounds on node degree for which the problems remain NP-complete.

An elderly man with long-standing pulmonary emphysema was seen with recent onset of steatorrhea and ascites. He had very low levels of serum α 1 -antitrypsin, hepatic cirrhosis, and intestinal mucosal atrophy. We believe that this combination of findings did not occur by chance. ( JAMA 231:273-276, 1975)

We give a characterization of all the planar drawings of a triangular graph through a system of equations and inequalities relating its angles; we also discuss minimality properties of the characterization. The characterization can be used: (1) to decide in linear time whether a given distribution of angles between the edges of a planar triangular graph can result in a planar drawing; (2) to reduce the problem of maximizing the minimum angle in a planar straight-line drawing of a planar triangular graph to a nonlinear optimization problem purely on a space of angles; (3) to give a characterization of the planar drawings of a triconnected graph through a system of equations and inequalities relating its angles; (4) to give a characterization of Delaunay triangulations through a system of equations and inequalities relating its angles; (5) to give a characterization of all the planar drawings of a triangular graph through a system of equations and inequalities relating the lengths of its edges; in turn, this result allows us to give a new characterization of the disc-packing representations of planar triangular graphs.