On Exact and Approximate Solutions for Hard Problems: An Alternative Look

We discuss in an informal, general audience style the da Costa-Doria conjecture about the independence of the P = NP hypothesis and try to briefly assess its impact on practical situations in economics. The paper concludes with a discussion of the Coppe-Cosenza procedure, which is an approximate, partly heuristic algorithm for allocation problems.

MoreLess

Year of publication:	2011
Authors:	Bartholo, R. S. ; Cosenza, C. A. ; Doria, F. A. ; Doria, M. ; Teixeira, A.
Institutions:	Dipartimento di Economia e Management, Università degli Studi di Trento
Subject:	P vs. NP \| allocation problem \| assignment problem \| traveling salesman \| exact solution for NP problems \| approximate solutions for NP problems \| undecidability \| incompleteness

More details

Extent:	application/pdf
Series:	ASSRU Discussion Papers.
Type of publication:	Book / Working Paper
Language:	English
Notes:	Number 1103
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10009024777