Stanford InfoLab Publication Server

Result Verification Algorithms for Optimization Problems.

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
Related URLs:Project Homepage
ID Code:99
Deposited By:Import Account
Deposited On:25 Feb 2000 16:00
Last Modified:02 Dec 2008 15:52

Download statistics

Repository Staff Only: item control page