• Login
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Browse

    All of DSpaceCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    Statistics

    View Usage StatisticsView Google Analytics Statistics

    Bin Packing with Advice

    Thumbnail
    View/Open
    201511005 (829.1Kb)
    Date
    2017
    Author
    Shah, Akash
    Metadata
    Show full item record
    Abstract
    "The framework of competitive analysis is often used to study the bin packing algorithms. Under this framework, the behavior of online algorithms is compared to an optimal offline algorithm on the worst possible input. In this thesis, we discuss the limitations of the competitive analysis and introduce the bin packing problem under the advice model. In competitive analysis, the focus on improving competitive ratio often results in sacrificing the average-case performance and therefore, many of the studied online algorithms have no practical significance. An alternative for analysis of online problems is the advice model which has received significant attention in the past few years. Under the advice model, an online algorithm receives a number of bits of advice about the unrevealed parts of the sequence. Generally, there is a trade-off between the size of the advice and the performance of online algorithms. The main goal of this thesis is to find whether the entire input distribution is required to improve the competitive ratio of an online algorithm or only partial information about the distribution is sufficient to improve the performance. It turns out that information about some portion of the distribution is enough to achieve reasonable competitive ratio. We have designed a heuristic under the assumption of such advice and compared its performance against standard bin packing heuristics.
    URI
    http://drsr.daiict.ac.in//handle/123456789/679
    Collections
    • M Tech Dissertations [923]

    Resource Centre copyright © 2006-2017 
    Contact Us | Send Feedback
    Theme by 
    Atmire NV
     

     


    Resource Centre copyright © 2006-2017 
    Contact Us | Send Feedback
    Theme by 
    Atmire NV