This paper considers weight-maximizing variants of the classical symmetric and asymmetric traveling-salesman problems. Like their weight-minimizing counterparts, these variants are MAX SNP-hard. We present the first nontrivial approximation algorithms for these problems. Our algorithm for directed graphs finds a tour whose weight is at least 38/63/spl ap/0.603 times the weight of a maximum-weight tour, and our algorithm for undirected graphs finds a tour whose weight is at least 5/7/spl ap/0.714 times optimal. These bounds compare favorably with the 1/2 and 2/3 bounds that can be obtained for undirected and directed graphs, respectively, by simply deleting the minimum-weight edge from each cycle of a maximum-weight cycle cover. Our algorithm for directed graphs can be used to improve several recent approximation results for the shortest-superstring problem.>

Article Free Access Share on Finding minimum-quotient cuts in planar graphs Authors: James K. Park View Profile , Cynthia A. Phillips View Profile Authors Info & Claims STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of ComputingJune 1993 Pages 766–775https://doi.org/10.1145/167088.167284Online:01 June 1993Publication History 24citation746DownloadsMetricsTotal Citations24Total Downloads746Last 12 Months20Last 6 weeks7 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Parallel searching in generalized Monge arrays with applications Share on Authors: A. Aggarwal IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NYView Profile , D. Kravets Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MAView Profile , J. Park Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MAView Profile , S. Sen Department of Computer Science, Duke University, Durham, NC Department of Computer Science, Duke University, Durham, NCView Profile Authors Info & Claims SPAA '90: Proceedings of the second annual ACM symposium on Parallel algorithms and architecturesMay 1990 Pages 259–268https://doi.org/10.1145/97444.97693Online:01 May 1990Publication History 11citation348DownloadsMetricsTotal Citations11Total Downloads348Last 12 Months4Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

A two-dimensional array A=(a/sub i,j/) is called monotone if the maximum entry in its ith row lies below or to the right of the maximum entry in its (i- 1)-st row. An array A is called totally monotone if every 2*2 subarray (i.e., every 2*2 minor) is monotone. The notion of two-dimensional totally monotone arrays is generalized to multidimensional arrays, and a wide variety of problems are exhibited involving computational geometry, dynamic programming, VLSI river routing, and finding certain kinds of shortest paths that can be solved efficiently by finding maxima in totally monotone arrays.>