home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / compress / 4787 < prev    next >
Encoding:
Text File  |  1993-01-25  |  1.9 KB  |  46 lines
  1. Newsgroups: comp.compression
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!caen!nic.umass.edu!news.amherst.edu!djweisbe
  3. From: djweisbe@unix.amherst.edu (David Weisberger)
  4. Subject: Re: Unix release? (Was etc.
  5. Message-ID: <C1EArp.KL@unix.amherst.edu>
  6. Sender: news@unix.amherst.edu (No News is Good News)
  7. Nntp-Posting-Host: amhux3.amherst.edu
  8. Organization: large
  9. X-Newsreader: TIN [version 1.1 PL7]
  10. References: <727889693snz@genesis.demon.co.uk>
  11. Date: Mon, 25 Jan 1993 05:47:49 GMT
  12. Lines: 32
  13.  
  14. Lawrence Kirby (fred@genesis.demon.co.uk) wrote:
  15. : In article <9cl333-@rpi.edu> sigma@degas.ipl.rpi.edu writes:
  16. : 
  17. : >madler@cco.caltech.edu (Mark Adler) writes:
  18. : >>Or perhaps you think that the other zipsplit optimizes the chunks
  19. : >>better.  I don't know what algorithm the other zipsplit uses, but
  20. : >>our's uses a simple "greedy" algorithm that achieves the optimum in
  21. : >>nearly all cases with typical distributions of entry sizes.  The
  22. : >>chunk optimization is an NP-complete problem, so there are lots of
  23. : >>approximate approaches to the solution.
  24. : >
  25. : >This is what's called the Knapsack Problem.  It's NP-complete, but since
  26.  
  27. This is actually the Bin Packing problem, not the Knapsack problem.
  28.  
  29. : The knapsack problem deals with a single knapsack (i.e. disk) and is NOT
  30. : NP-complete. It's a common example of dynamic programming where the optimal
  31.  
  32. The Knapsack problem sure is NP complete.  I believe the following
  33. explanation is correct, if simple (check in comp.theory, though):
  34.  
  35. There is an algorithm which is linear in N, the number of items, but
  36. the specification of N is of length proportional to log N, so the
  37. running time is actually exponential in the length of the input.
  38.  
  39. Just a humble undergrad,
  40.   David
  41.  
  42. --
  43. Davebo                    "Don't believe I'm taken in by stories I have heard.
  44.                            I just read the Daily News and swear by every word."
  45. djweisbe@unix.amherst.edu
  46.