NP-completeness question

Article View: comp.theory

Article #1828

#1828

From: Chip Klostermeyer
Date: Wed, 19 Jun 1991 15:04

11 lines
896 bytes

I would appreciate any references to a pseudo-polynomial time algorithm
or a proof of NP-completeness in the strong sense for the zero-one
integer programming problem. 
Also, any references to an algorithm for finding lower bounds for
solutions to zero-one integer programming problems would be welcome.

E-mail to wk@reef.cis.ufl.edu
I will summarize to net.

Thanks
Chip Klostermeyer

Technical Details

Message-ID: <29269@uflorida.cis.ufl.EDU>

Path:

arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!zaphod.mps.ohio-state.edu!sample.eng.ohio-state.edu!purdue!haven.umd.edu!uflorida!reef.cis.ufl.edu!wk

Show Full Headers

Complete Article Headers

Path: arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!zaphod.mps.ohio-state.edu!sample.eng.ohio-state.edu!purdue!haven.umd.edu!uflorida!reef.cis.ufl.edu!wk
From: wk@reef.cis.ufl.edu (Chip Klostermeyer)
Newsgroups: comp.theory
Subject: NP-completeness question
Keywords: NP-complete, NP-complete in strong sense, zero-one integer prog.
Message-ID: <29269@uflorida.cis.ufl.EDU>
Date: 19 Jun 91 15:04:47 GMT
Sender: news@uflorida.cis.ufl.EDU
Organization: UF CIS Dept.
Lines: 11