Gupta, H. (1995) Result Verification Algorithms for Optimization Problems. Technical Report. Stanford. (Publication Note: UIUC, 1995.)
In this article we discuss the design of result verification algorithms for optimization problems. In particular, we design time-optimal result verification algorithms which verify the solution of all-pairs shortest paths, maximum-flow in a network, and matching problems. We prove that polynomial-time verification algorithms for NP-complete problems do not exist exist, unless P = NP. Result verification problems for most of the NP-hard problems are not believed to be in NP. W e also consider verification algorithms for approximation algorithms for NP-complete and NP-hard problems.
| Item Type: | Techreport (Technical Report) | |
|---|---|---|
| Subjects: | Computer Science > Data Mining | |
| Projects: | MIDAS | |
| Related URLs: | Project Homepage | http://infolab.stanford.edu/midas/midas.html |
| ID Code: | 99 | |
| Deposited By: | Import Account | |
| Deposited On: | 25 Feb 2000 16:00 | |
| Last Modified: | 02 Dec 2008 15:52 |
Repository Staff Only: item control page