Approximation algorithm paper

Article View: comp.theory

Article #1936

#1936

From: David Levine
Date: Mon, 11 Jan 1993 22:55

7 lines
908 bytes

Could someone provide a reference (or email address of an author(s)) to the
work by S. Arora, M. Sudan, R. Motwani, C. Lund, and M. Szegedy mentioned in
New Scientist 12/12/92:  "Their result implies that if P != NP, then there is
a threshold beyond which it is just as hard to find a good approximation
algorithm that will always work as it is to find a good solution."

Thanks --dave

Technical Details

Message-ID: <7267929429746@jadoube.mcs.anl.gov>

Path:

arc1-ca.pugleaf.net!sparky!uunet!paladin.american.edu!howland.reston.ans.net!spool.mu.edu!uwm.edu!ux1.cso.uiuc.edu!milo.mcs.anl.gov!jadoube.mcs.anl.gov!levine

Show Full Headers

Complete Article Headers

Newsgroups: comp.theory
Path: arc1-ca.pugleaf.net!sparky!uunet!paladin.american.edu!howland.reston.ans.net!spool.mu.edu!uwm.edu!ux1.cso.uiuc.edu!milo.mcs.anl.gov!jadoube.mcs.anl.gov!levine
From: levine@jadoube.mcs.anl.gov (David Levine)
Subject: Approximation algorithm paper
Message-ID: <7267929429746@jadoube.mcs.anl.gov>
Sender: usenet@mcs.anl.gov
Nntp-Posting-Host: jadoube.mcs.anl.gov
Organization: Argonne National Laboratory, Chicago, Illinois
Distribution: comp.theory
Date: Mon, 11 Jan 1993 22:55:42 GMT
Lines: 8