I've had difficulty finding out the precise capacity of a DVD-R disk, but thanks to an obscure footnote in the DVD Studio Pro documentation, now I know. A DVD-R holds 4,699,979,766 bytes. I use Toast to burn discs, it only reports disc size in blocks, and I've never figured out how big a block is. I'm sure it's documented somewhere but I sure can't find it.
I like doing DVD-R backups but it's always a hassle to create archives just the right size. I like to use as much of the disk as possible, with no unused space. But since the files you're burning never precisely add up to 4,699,979,766 bytes, there's always some unused space left over. It can take a considerable amount of effort to find a proper mix of file sizes to make a full DVD image. This particular problem may seem like a lot of extra effort expended chasing after efficiency, but the problem has also occupied some of the great mathematical minds of our time. It is known as the Bin-Packing Problem. It has been mathematically proven that there is no optimal bin packing algorithm, so I feel a lot better when I have trouble with the same problem when preparing DVD-R images.


Not quite right, Charles.
It has been proven that bin-packing is NP-complete. It is not known whether NP=P.
If this were known, then solving one NP problem would solve all of them (or something like that; too many beers this evening (it's 20:26 CET here)).


I had to gloss over quite a bit in my brief reference. Perhaps I should have said there is an optimal algorithm but there is no perfect algorithm.

Leave a comment

About this Entry

This page contains a single entry by Charles published on June 4, 2003 12:00 PM.

BlogTV: How To Start A Crime Wave was the previous entry in this blog.

Presidential Breakfast is the next entry in this blog.

Find recent content on the main index or look in the archives to find all content.



Powered by Movable Type 5.13-en