As streaming video over the Internet becomes increasingly popular, cost-effective caching of these large multimedia documents has become of utmost importance. For large media objects, such as a 2-hour video, treating the whole video as a single web object for caching is not appropriate. The paper presents reservation-based caching algorithms to evaluate a segment-based buffer management approach for off-line scheduling and caching in polynomial time. The cache admission and replacement policies decide when, where and for how long videos will be cached. Requests for videos are available a priori.