Library

X
Language
Preferred search index
Number of Hits per Page
Default Sort Criterion
Default Sort Ordering
Size of Search History
Default Email Address
Default Export Format
Default Export Encoding
Facet list arrangement
Maximum number of values per filter
Auto Completion
Feed Format
Maximum Number of Items per Feed
Permalink If you want to be able to use settings permanently, you must save your settings and then set a Bookmark to the permalink
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
  • Articles: DFG German National Licenses  (2)
  • 05B40  (1)
  • Cutting stock problems  (1)
  • 1
    Electronic Resource
    Electronic Resource
    Packing random intervals (1995)
    Springer
    Probability theory and related fields 102 (1995), S. 105-121 
    Details
    ISSN: 1432-2064
    Keywords: 60D05 ; 05B40 ; 52A22
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary Letn random intervalsI 1, ...,I n be chosen by selecting endpoints independently from the uniform distribution on [0.1]. Apacking is a pairwise disjoint subset of the intervals; itswasted space is the Lebesgue measure of the points of [0,1] not covered by the packing. In any set of intervals the packing with least wasted space is computationally easy to find; but its expected wasted space in the random case is not obvious. We show that with high probability for largen, this “best” packing has wasted space $$O(\frac{{\log ^2 n}}{n})$$ . It turns out that if the endpoints 0 and 1 are identified, so that the problem is now one of packing random arcs in a unit-circumference circle, then optimal wasted space is reduced toO(1/n). Interestingly, there is a striking difference between thesizes of the best packings: about logn intervals in the unit interval case, but usually only one or two arcs in the circle case.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01295224
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Packings in two dimensions: Asymptotic average-case analysis of algorithms (1993)
    Springer
    Algorithmica 9 (1993), S. 253-277 
    Details
    ISSN: 1432-0541
    Keywords: Average-case analysis ; Cutting stock problems ; Two-dimensional packing ; Bin packing
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract New approximation algorithms for packing rectangles into a semi-infinite strip are introduced in this paper. Within a standard probability model, an asymptotic average-case analysis is given for the wasted space in the packings produced by these algorithms. An off-line algorithm is presented along with a proof that it wastes θ(√/n)space on the average, wheren is the number of rectangles packed. This result is known to apply to optimal packings as well. Several on-line shelf algorithms are also analyzed. Withn assumed known in advance, one such algorithm is described and shown to waste θ(n 2/3) space on the average. It is proved that this result also characterizes optimal on-line shelf packings. For a very general class of linear-time algorithms, it is shown that a constant (nonzero) fraction of the space must be wasted on the average for alln, and a lower bound on this fraction in terms of algorithm parameters is given. Finally, the paper discusses the implications of the above results for dynamic packing and two-dimensional bin-packing problems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01190899
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...