home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / sci / math / 9460 < prev    next >
Encoding:
Internet Message Format  |  1992-07-23  |  1.6 KB
  1. Xref: sparky sci.math:9460 sci.math.num-analysis:2279 sci.math.symbolic:2058
  2. Newsgroups: sci.math,sci.math.num-analysis,sci.math.symbolic
  3. Path: sparky!uunet!gatech!usenet.ins.cwru.edu!agate!linus!linus.mitre.org!fatima!bs
  4. From: bs@fatima.mitre.org (Robert D. Silverman)
  5. Subject: Re: Lattice points in a polytope? (How to find all of them?)
  6. Message-ID: <1992Jul23.160552.6153@linus.mitre.org>
  7. Keywords: polytope, integer points
  8. Sender: news@linus.mitre.org (News Service)
  9. Nntp-Posting-Host: fatima.mitre.org
  10. Organization: Research Computer Facility, MITRE Corporation, Bedford, MA
  11. References: <BruKLH.DBz@watdragon.waterloo.edu>
  12. Date: Thu, 23 Jul 1992 16:05:52 GMT
  13. Lines: 28
  14.  
  15. In article <BruKLH.DBz@watdragon.waterloo.edu> xjzhu@jeeves.waterloo.edu (Xiao Jun Zhu) writes:
  16. :Hi, there:
  17. :
  18. :   I am in need of an efficient program or algorithm(prefer in C) which can 
  19. :find all the integer points in a polytope defined by sets of inequalities.
  20. :(Suppose that I know that the number of lattice points is not so huge.)
  21. :If you know such a thing exists, please send a message to me. Thanks very
  22. :much for your help.
  23.  
  24. There are probabalistic methods that work in polynomial time (in RP).
  25. However, they only give approximate answers.
  26.  
  27. If you need an exact answer I'm afraid that the problem is NP-Complete.
  28. There is no 'efficient' way of doing it.
  29.  
  30. See, for example, 
  31.  
  32. Theory of Linear and Integer Programming
  33. Alexander Schrijver
  34. John Wiley & Sons. ISBN 0 471 90854 1
  35.  
  36. I might also suggest Schrijver's book Polyhedral Combinatorics
  37.  
  38. --
  39. Bob Silverman
  40. These are my opinions and not MITRE's.
  41. Mitre Corporation, Bedford, MA 01730
  42. "You can lead a horse's ass to knowledge, but you can't make him think"
  43.