Browse Prior Art Database

P-Complete Apprixation Problems

IP.com Disclosure Number: IPCOM000128525D
Original Publication Date: 1975-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 21 page(s) / 45K

Publishing Venue

Software Patent Institute

Related People

Sartaj Salmi: AUTHOR [+4]

Abstract

We present a linear time approximation algorithm for the k-Max Cut problem. For other P-Complete problems such as: travelling salesperson, cycle covers, 0-1 integer programming, multa commodity network flows, quadratic assignment etc. it is shown that the approximation problem is also P-Complete.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 12% of the total text.

Page 1 of 21

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

P-Complete Apprixation Problems

Sartaj Salmi and Teofilo Gonzalez

0400212 Computer, Information, and Control Sciences Department Institute of Technology University of Minnesota Minneapolis, Minnesota * Technical Report 75-12 June, 1975

This research was supported in part by NSF Grant DCR 74-;0081.

An earlier version of some of the results in this paper was presented at the 15th IEEE Symposium on Switching and Automata Theory, 1974.

Cover design courtesy of, Ruth and Jay Leavitt

I,

P-Complete Approximation Problems

Sartaj Sahni and Teofilo Gonzalez University of Minnesota

Abstract

We present a linear time approximation algorithm for the k-Max Cut problem. For other P- Complete problems such as: travelling salesperson, cycle covers, 0-1 integer programming, multa commodity network flows, quadratic assignment etc. it is shown that the approximation problem is also P-Complete.

Key Words and Phrases: P-Complete, approximation algorithm, polynomial complexity, k-Max Cut, travelling salesperson, cycle covers, multicommodity network flows, quadratic assignment, integer programming, general partitions, k-Min Cluster.

CR Categories: 5.23, 5.25, 5.32, 5.40 . t This research was supported in part by NSF grant DCR 74-10081.

An earlier version of some of the results in this paper was presented at the 15th IEEE Symposium on Switching and Automata Theory, 1974.

1. Introduction

Our notion of P-Complete corresponds to the one used in [6]. A problem, L, will he said to be P- Complete iff the following holds: L can be solved in polynomial deterministic time iff the class of nondeterministic polynomial time languages is the same as deterministic polynomial time languages (i.e. P = NP). Knuth [5] suggests the terminology NP-Complete. However, his notion of "completeness" is that of Karp [4]. Since the equivalence or nonequivalence of the two notions is not known, we will use the term NP-Complete for problems that can be shown complete with Karpls.definition and P-Complete for those which require the definition of [6]. The reader unfam-iliar with P-Complete problems is referred to [4] and [6]. All problems that are NP-

University of Minnesota Page 1 Dec 31, 1975

Page 2 of 21

P-Complete Apprixation Problems

Complete (i.e. complete under Karp's definitions) are also P-Complete [2 and 6]. The reverse is unknown. Since it appears that P 0 NP, the P-Complete problems probably have no polynomial solution. Many of these problems, especially the optimization problems, are of .practical significance. Often, as in the case of the Knapsack problem [7], approximate solutions (i.e. feasible solutions that are guaranteed to be 'reasonably! close to the optimal) would be acceptable so long as they can be obtained 'quickly' (e.g. by an 0(nk) algorithm for small k). Johnson [3] and Sahni [7] have studied some P-Complete problems with respect to obtaining 'good' (i.e. polynomial) approximate algorithms. (Fo...