University of Maryland LibrariesDigital Repository at the University of Maryland
    • Войти
    Просмотр элемента 
    •   Главная
    • College of Computer, Mathematical & Natural Sciences
    • Computer Science
    • Technical Reports from UMIACS
    • Просмотр элемента
    •   Главная
    • College of Computer, Mathematical & Natural Sciences
    • Computer Science
    • Technical Reports from UMIACS
    • Просмотр элемента
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Approximation Algorithms and Heuristics for the Dynamic Storage Allocation Problem

    Thumbnail
    Открыть
    CS-TR-4024.ps (255.0Kb)
    No. of downloads: 245

    Auto-generated copy of CS-TR-4024.ps (93.33Kb)
    No. of downloads: 567

    Дата
    1999-06-08
    Автор
    Murthy, Praveen K.
    Bhattacharyya, Shuvra S.
    Metadata
    Показать полную информацию
    Аннотации
    In this report, we look at the problem of packing a number of arrays in memory efficiently. This is known as the dynamic storage allocation problem (DSA) and it is known to be NP-complete. We develop some simple, polynomial-time approximation algorithms with the best of them achieving a bound of 4 for a sub-class of DSA instances. We report on an extensive experimental study on the FirstFit heuristic and show that the average-case performance on random instances is within 7% of the optimal value. Also cross-referenced as UMIACS-TR-99-31
    URI
    http://hdl.handle.net/1903/1013
    Collections
    • Technical Reports from UMIACS
    • Technical Reports of the Computer Science Department

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility
     

     

    Просмотр

    Весь DSpaceСообщества и коллекцииДата публикацииАвторыНазванияТематикаЭта коллекцияДата публикацииАвторыНазванияТематика

    Моя учетная запись

    ВойтиРегистрация
    Pages
    About DRUMAbout Download Statistics

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility