On some packing problem related to dynamic storage allocation

DOI10.1051/ITA/1988220404871MaRDI QIDQ3830539zbMATH OpenOpenAlexFDO

Authors Maciej Ślusarek, Marek Chrobak

Publication date 1988

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/92318

zbMATH Keywords

approximation algorithmdynamic storage allocationrectangle packing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Recommendations

• Dynamic, first-fit packings in two or more dimensions
• Two-dimensional rectangle packing: On-line methods and results
• scientific article; zbMATH DE number 634028
• Packings in two dimensions: Asymptotic average-case analysis of algorithms
• GENERALIZED FIRST-FIT ALGORITHMS IN TWO AND THREE DIMENSIONS

Cites work

• A algorithm for two-dimensional packing
• A two-dimensional bin-packing model of preemptive, FIFO storage allocation
• An Introduction to Combinatorial Models of Dynamic Storage Allocation
• An off-line storage allocation algorithm
• Bounds for Some Functions Concerning Dynamic Storage Allocation
• Dynamic Bin Packing
• scientific article; zbMATH DE number 4043214 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1178976 (Why is no real title available?)
• Lower bounds for on-line two-dimensional packing algorithms
• Shelf Algorithms for Two-Dimensional Packing Problems

Cited in

(35)

• Variable sized online interval coloring with bandwidth
• An off-line storage allocation algorithm
• A polynomial time approximation algorithm for dynamic storage allocation
• Two-dimensional rectangle packing: On-line methods and results
• On the performance guarantee of first fit for sum coloring
• On spectrum assignment in elastic optical tree-networks
• Coloring interval graphs with First-Fit
• Space defragmentation for packing problems
• On-line dimension for posets excluding two long incomparable chains
• On-line partitioning of width \(w\) posets into \(w^{O(\log\log w)}\) chains
• On-line coloring and cliques covering for \(\mathbb K_{s,t}\)-free graphs
• A subexponential upper bound for the on-line chain partitioning problem
• Forbidden structures for efficient first-fit chain partitioning (extended abstract)
• OPT versus LOAD in dynamic storage allocation
• Dynamic, first-fit packings in two or more dimensions
• OPTVersusLOADin Dynamic Storage Allocation
• Optimal on-line coloring of circular arc graphs
• First-fit coloring on interval graphs has performance ratio at least 5
• First-fit coloring of bounded tolerance graphs
• On the Max Coloring Problem
• Complexity and online algorithms for minimum skyline coloring of intervals
• Improved lower bound on the on-line chain partitioning of semi-orders with representation
• scientific article; zbMATH DE number 7758354 (Why is no real title available?)
• On-line interval graphs coloring — Modification of the First-Fit algorithm and its performance ratio
• Online coloring of short intervals
• Improved dynamic colouring of sparse graphs
• First-Fit is linear on posets excluding two long incomparable chains
• On the \textsc{FirstFit} algorithm for online unit-interval coloring
• On the max coloring problem
• On the on-line coloring of unit interval graphs with proper interval representation
• On-line chain partitions of orders: a survey
• Online promise problems with online width metrics
• An improved algorithm for online coloring of intervals with bandwidth
• A note on first-fit coloring of interval graphs
• Online interval coloring with packing constraints

This page was built for publication: On some packing problem related to dynamic storage allocation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3830539)