View in EDS PDF Full Text

OPT VERSUS LOAD IN DYNAMIC STORAGE ALLOCATION.

Saved in:
Bibliographic Details
Title: OPT VERSUS LOAD IN DYNAMIC STORAGE ALLOCATION.
Authors: Buchsbaum, Adam L.1 alb@research.att.com, Karloff, Howard1 howard@research.att.com, Kenyon, Claire2 kenyon@lix.polytechnique.fr, Reingold, Nick1 reingold@research.att.com, Thorup, Mikkel1 mthorup@research.att.com
Source: SIAM Journal on Computing. 2004, Vol. 33 Issue 2, p632-646. 15p.
Subjects: Dynamic storage allocation (Computer science), Algorithms, Polynomials, Algebra, Computer programming, Digital communications
Abstract: Dynamic storage allocation is the problem of packing given axis-aligned rectangles into a horizontal strip of minimum height by sliding the rectangles vertically but not horizontally. Where L = LOAD is the maximum sum of heights of rectangles that intersect any vertical line and OPT is the minimum height of the enclosing strip, it is obvious that OPT ≥ LOAD; previous work showed that OPT < 3 LOAD. We continue the study of the relationship between OPT and LOAD, proving that OPT = L + O((hmax/L)1/7)L, where hmax is the maximum job height. Conversely, we prove that for any ϵ > 0, there exists a c > 0 such that for all sufficiently large integers hmax, there is a dynamic storage allocation instance with maximum job height hmax, maximum load at most L, and OPT ≥ L + c(hmax/L)1/2+ϵL, for infinitely many integers L. En route, we construct several new polynomial-time approximation algorithms for dynamic storage allocation, including a (2 + ϵ)-approximation algorithm for the general case and polynomial-time approximation schemes for several nafliral special cases. [ABSTRACT FROM AUTHOR]
Copyright of SIAM Journal on Computing is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Links:
  – Type: pdflink
Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 13266085
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: OPT VERSUS LOAD IN DYNAMIC STORAGE ALLOCATION.
– Name: Author
  Label: Authors
  Group: Au
  Data: &lt;searchLink fieldCode=&quot;AR&quot; term=&quot;%22Buchsbaum%2C+Adam+L%2E%22&quot;&gt;Buchsbaum, Adam L.&lt;/searchLink&gt;&lt;relatesTo&gt;1&lt;/relatesTo&gt;&lt;i&gt; alb@research.att.com&lt;/i&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;AR&quot; term=&quot;%22Karloff%2C+Howard%22&quot;&gt;Karloff, Howard&lt;/searchLink&gt;&lt;relatesTo&gt;1&lt;/relatesTo&gt;&lt;i&gt; howard@research.att.com&lt;/i&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;AR&quot; term=&quot;%22Kenyon%2C+Claire%22&quot;&gt;Kenyon, Claire&lt;/searchLink&gt;&lt;relatesTo&gt;2&lt;/relatesTo&gt;&lt;i&gt; kenyon@lix.polytechnique.fr&lt;/i&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;AR&quot; term=&quot;%22Reingold%2C+Nick%22&quot;&gt;Reingold, Nick&lt;/searchLink&gt;&lt;relatesTo&gt;1&lt;/relatesTo&gt;&lt;i&gt; reingold@research.att.com&lt;/i&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;AR&quot; term=&quot;%22Thorup%2C+Mikkel%22&quot;&gt;Thorup, Mikkel&lt;/searchLink&gt;&lt;relatesTo&gt;1&lt;/relatesTo&gt;&lt;i&gt; mthorup@research.att.com&lt;/i&gt;
– Name: TitleSource
  Label: Source
  Group: Src
  Data: &lt;searchLink fieldCode=&quot;JN&quot; term=&quot;%22SIAM+Journal+on+Computing%22&quot;&gt;SIAM Journal on Computing&lt;/searchLink&gt;. 2004, Vol. 33 Issue 2, p632-646. 15p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: &lt;searchLink fieldCode=&quot;DE&quot; term=&quot;%22Dynamic+storage+allocation+%28Computer+science%29%22&quot;&gt;Dynamic storage allocation (Computer science)&lt;/searchLink&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;DE&quot; term=&quot;%22Algorithms%22&quot;&gt;Algorithms&lt;/searchLink&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;DE&quot; term=&quot;%22Polynomials%22&quot;&gt;Polynomials&lt;/searchLink&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;DE&quot; term=&quot;%22Algebra%22&quot;&gt;Algebra&lt;/searchLink&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;DE&quot; term=&quot;%22Computer+programming%22&quot;&gt;Computer programming&lt;/searchLink&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;DE&quot; term=&quot;%22Digital+communications%22&quot;&gt;Digital communications&lt;/searchLink&gt;
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Dynamic storage allocation is the problem of packing given axis-aligned rectangles into a horizontal strip of minimum height by sliding the rectangles vertically but not horizontally. Where L = LOAD is the maximum sum of heights of rectangles that intersect any vertical line and OPT is the minimum height of the enclosing strip, it is obvious that OPT ≥ LOAD; previous work showed that OPT &lt; 3 LOAD. We continue the study of the relationship between OPT and LOAD, proving that OPT = L + O((hmax/L)1/7)L, where hmax is the maximum job height. Conversely, we prove that for any &amp;epsiv; &gt; 0, there exists a c &gt; 0 such that for all sufficiently large integers hmax, there is a dynamic storage allocation instance with maximum job height hmax, maximum load at most L, and OPT ≥ L + c(hmax/L)1/2+&amp;epsiv;L, for infinitely many integers L. En route, we construct several new polynomial-time approximation algorithms for dynamic storage allocation, including a (2 + &amp;epsiv;)-approximation algorithm for the general case and polynomial-time approximation schemes for several nafliral special cases. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: &lt;i&gt;Copyright of SIAM Journal on Computing is the property of Society for Industrial &amp; Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder&#39;s express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.&lt;/i&gt; (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=13266085
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1137/S0097539703423941
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 15
        StartPage: 632
    Subjects:
      – SubjectFull: Dynamic storage allocation (Computer science)
        Type: general
      – SubjectFull: Algorithms
        Type: general
      – SubjectFull: Polynomials
        Type: general
      – SubjectFull: Algebra
        Type: general
      – SubjectFull: Computer programming
        Type: general
      – SubjectFull: Digital communications
        Type: general
    Titles:
      – TitleFull: OPT VERSUS LOAD IN DYNAMIC STORAGE ALLOCATION.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Buchsbaum, Adam L.
      – PersonEntity:
          Name:
            NameFull: Karloff, Howard
      – PersonEntity:
          Name:
            NameFull: Kenyon, Claire
      – PersonEntity:
          Name:
            NameFull: Reingold, Nick
      – PersonEntity:
          Name:
            NameFull: Thorup, Mikkel
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 04
              Text: 2004
              Type: published
              Y: 2004
          Identifiers:
            – Type: issn-print
              Value: 00975397
          Numbering:
            – Type: volume
              Value: 33
            – Type: issue
              Value: 2
          Titles:
            – TitleFull: SIAM Journal on Computing
              Type: main
ResultId 1