home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / compress / 4784 < prev    next >
Encoding:
Internet Message Format  |  1993-01-24  |  2.1 KB
  1. Path: sparky!uunet!seismo!darwin.sura.net!gatech!usenet.ins.cwru.edu!agate!doc.ic.ac.uk!pipex!demon!genesis.demon.co.uk!fred
  2. From: fred@genesis.demon.co.uk (Lawrence Kirby)
  3. Newsgroups: comp.compression
  4. Subject: Re: Unix release? (Was etc.
  5. Message-ID: <727889693snz@genesis.demon.co.uk>
  6. Date: 24 Jan 93 15:34:53 GMT
  7. References: <9cl333-@rpi.edu>
  8. Sender: usenet@demon.co.uk
  9. Organization: BT
  10. Lines: 33
  11. X-Mailer: Simple NEWS 1.90 (ka9q DIS 1.19)
  12.  
  13. In article <9cl333-@rpi.edu> sigma@degas.ipl.rpi.edu writes:
  14.  
  15. >madler@cco.caltech.edu (Mark Adler) writes:
  16. >>Or perhaps you think that the other zipsplit optimizes the chunks
  17. >>better.  I don't know what algorithm the other zipsplit uses, but
  18. >>our's uses a simple "greedy" algorithm that achieves the optimum in
  19. >>nearly all cases with typical distributions of entry sizes.  The
  20. >>chunk optimization is an NP-complete problem, so there are lots of
  21. >>approximate approaches to the solution.
  22. >
  23. >This is what's called the Knapsack Problem.  It's NP-complete, but since
  24. >your knapsack is usually relatively small compared to the total size of the
  25. >files, an early-out algorithm which avoids combinations which will
  26. >obviously not fit actually has to check very few combinations.  Even with
  27. >four hundred files, I've never had to check more than 30000 combinations
  28. >(well, my program does - not myself by hand) to get a perfect fit.
  29. >
  30.  
  31. The knapsack problem deals with a single knapsack (i.e. disk) and is NOT
  32. NP-complete. It's a common example of dynamic programming where the optimal
  33. solution can be derived in order NM time where N is the number of items
  34. (files) and M is the knapsack size (i.e. number of disk allocation units). To
  35. put it another way for a fixed disk size (such as 1.44MB) the algorithm is
  36. linear in N.
  37.  
  38. Optimising allocation over multiple volumes is more complex and the solution
  39. isn't in general the same as optimising each volume in sequence. This *may*
  40. be NP-complete, but I would need to be convinced!
  41.  
  42. -----------------------------------------
  43. Lawrence Kirby | fred@genesis.demon.co.uk
  44. Wilts, England | 70734.126@compuserve.com
  45. -----------------------------------------
  46.