home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / theory / 2392 < prev    next >
Encoding:
Internet Message Format  |  1992-11-11  |  1.8 KB
  1. Path: sparky!uunet!cis.ohio-state.edu!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!ira.uka.de!chx400!sicsun!disuns2!/!diderich
  2. From: diderich@di.epfl.ch (Claude G. Diderich)
  3. Newsgroups: comp.theory
  4. Subject: How to approximate the following NP-complete problem?
  5. Keywords: NP, NP-complete, Ptas, Apx, Max SNP
  6. Message-ID: <1992Nov11.095204@disuns2.epfl.ch>
  7. Date: 11 Nov 92 08:52:04 GMT
  8. Sender: news@disuns2.epfl.ch
  9. Reply-To: diderich@di.epfl.ch (Claude G. Diderich)
  10. Followup-To: diderich@di.epfl.ch (Claude G. Diderich)
  11. Organization: Ecole Polytechnique Federale de Lausanne, Suisse
  12. Lines: 30
  13. Nntp-Posting-Host: disuns2.epfl.ch
  14.  
  15. Dear reader,
  16.  
  17. I am studying the complexity of the following problem. I am especially
  18. interested  in classifying this problem in any apporximation class
  19. (like Ptas, Apx, Max SNP, etc...). Do you know of any references or
  20. results on this subject? Any personal ideas are greatly appreciated!
  21. Please e-mail and I will summarize.
  22.  
  23. Here is the problem:
  24.     You have a set of p linear equations of the form
  25.     a_{i,1} x_1 + ... + a_{i,v} x_v = b_i for i \in {1..p}.
  26.     Find a subset of equations that are satisfiable, e.g. that
  27.     have a solution (not necessarily unique) and that is maximal
  28.     in its dimension.
  29.  
  30. The problem can be solved in polynomial time if the number of
  31. variables v is constant. 
  32.  
  33. But no approximation results are known to me by this time.
  34.  
  35. Thanks all theory folk for reading this,
  36.  
  37. Claude G Diderich
  38.  
  39. ---------------------------------------------------------------------------
  40. Claude G. Diderich                            Internet: diderich@di.epfl.ch
  41. 30, Avenue S.Reymondin  --  CH-1009 Pully (VD)  --  Switzerland  --  Europe
  42.  
  43. ``Imagination is more important than knowledge''            Albert Einstein
  44. ---------------------------------------------------------------------------
  45.