Several polynomial time algorithms finding “good,” but not necessarily optimal, tours for the traveling salesman problem are considered. We measure closeness of a tour by ratio obtained length to minimal length. For nearest neighbor method, we show is bounded above logarithmic function number nodes. also provide lower bound on worst case. A class approximation methods call insertion studied, and these shown have upper bound. two specific methods, which cheapest insertion, constant 2,...

Abstract Unit disk graphs are intersection of circles unit radius in the plane. We present simple and provably good heuristics for a number classical NP‐hard optimization problems on graphs. The considered include maximum independent set, minimum vertex cover, coloring, dominating set. also an on‐line coloring heuristic which achieves competitive ratio 6 Our do not need geometric representation Geometric representations used only establishing performance guarantees heuristics. Several our...

A distributed database system is one in which the spread among several sites and application programs “move” from site to access update data they need. The concurrency control that portion of responds read write requests programs. Its job maintain global consistency while ensuring termination not prevented by phenomena such as deadlock. We assume each individual has its own local at can only communicate with controls other when an program moves site, terminates, or aborts. This paper...

The dispersion problem arises in selecting facilities to maximize some function of the distances between facilities. also nondominated solutions for multiobjective decision making. It is known be NP-hard under two objectives: maximizing minimum distance (MAX-MIN) any pair and average (MAX-AVG). We consider question obtaining near-optimal solutions. MAX-MIN, we show that if do not satisfy triangle inequality, there no polynomial-time relative approximation algorithm unless P = NP. When...

article Free Access Share on Programmed Grammars and Classes of Formal Languages Author: Daniel J. Rosenkrantz View Profile Authors Info & Claims Journal the ACMVolume 16Issue 1pp 107–131https://doi.org/10.1145/321495.321504Published:01 January 1969Publication History 192citation797DownloadsMetricsTotal Citations192Total Downloads797Last 12 Months48Last 6 weeks6 Get Citation AlertsNew Alert added!This alert has been successfully added will be sent to:You notified whenever a record that you...

Left corner parsing refers to a class of procedures in which the productions are recognized particular order is different than both bottom up and top down. Each production after its left descendant but before other descendants. Procedures this have occurred frequently compiler literature. In paper grammars, called LC (k) defined shown be exactly those grammars for certain canonical pushdown machine that does deterministic. A subset LC(k) strong can deterministically parsed by simplified...

Article Free Access Share on Many birds with one stone: multi-objective approximation algorithms Authors: R. Ravi View Profile , M. V. Marathe S. D. J. Rosenkrantz H. B. Hunt Authors Info & Claims STOC '93: Proceedings of the twenty-fifth annual ACM symposium Theory ComputingJune 1993 Pages 438–447https://doi.org/10.1145/167088.167209Online:01 June 1993Publication History 103citation672DownloadsMetricsTotal Citations103Total Downloads672Last 12 Months27Last 6 weeks2 Get Citation AlertsNew...

We study the problem of finding small trees. Classical network design problems are considered with additional constraint that only a specified number k nodes required to be connected in solution. A prototypical example is kMST which we require tree minimum weight spanning at least an edge-weighted graph. show NP-hard even for points Euclidean plane. provide approximation algorithms performance ratio $2\sqrt{k} $ general case and $O(k^{1/4} )$ Polynomial-time exact solutions also presented...

Several polynomial time algorithms finding "good," but not necessarily optimal, tours for the traveling salesman problem are considered. For nearest neighbor method, worst case ratio of obtained tour to optimal is shown increase logarithmically with number cities. another which we call insertion approach 2 as cities increases. It also that any n ≥ 8, there problems having k-optimal all k ≤ n/4, and respect 2(1 -1/n).

Associated with the write of a database entity is both before or old value, and after new value. Concurrency can be increased by allowing other transactions to read values given transaction. The ramifications this, particularly on distributed system in which limited communications desirable, are investigated. A careful distinction made between design decisions concerning responses read/write requests. Two schemes for producing such controls given, one scheme systems where processes committed...

The relationship between the set of productions a context-free grammar and corresponding defining equations is first pointed out. closure operation on matrix strings defined this concept used to formalize solution linear equations. A procedure then given for rewriting in Greibach normal form, where replacements string each production begins with terminal symbol. An additional so that replacement both ends Neither requires evaluation regular expressions over total vocabulary grammar, as...

We develop a graph-theoretic model for service-oriented networks and propose metrics that quantify the resilience of such under node edge failures. These are based on topological structure network manner in which services distributed over network. present efficient algorithms to determine maximum number failures can be tolerated by given rely known computing minimum cuts graphs. also optimally allocating so resulting tolerate single or derived through careful analysis decomposition...

Commercial distributed database systems generally support an optional protocol that provides loose consistency of replicas, allowing replicas to be inconsistent for some time. In such a protocol, each replicated data item is assigned primary copy site. Typically, transaction updates only the copies items, with other deferred until after commits. After commits, its are sent transactionally sites containing secondary copies. We investigate model underlying above protocol. show global...