scientific article

zbMath0759.90043MaRDI QIDQ4002885

George S. Lueker, Edward G. jun. Coffman

Publication date: 18 September 1992

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

partitioningapproximate solutionsprobabilistic analysisbin packingmakespan scheduling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Applications of queueing theory (congestion, allocation, storage, traffic, etc.) (60K30)

Related Items (38)

Partitioning ideal sets ⋮ New mixed-integer linear programming model for solving the multidimensional multi-way number partitioning problem ⋮ Order of decay of the wasted space for a stochastic packing problem. ⋮ Assigning service requests in voice-over-internet gateway multiprocessors ⋮ Optimal packing of similar triangles ⋮ Bin-packing and matchings in threshold graphs ⋮ The modified differencing method for the set partitioning problem with cardinality constraints ⋮ Stochastic simulations of two-dimensional composite packings ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ Average-case performance analysis of an approximation algorithm for maximum subset sum using recurrence relations ⋮ Probabilistic quality estimations for combinatorial optimization problems ⋮ Algorithmic obstructions in the random number partitioning problem ⋮ Pattern minimisation in cutting stock problems ⋮ Packing rectangles and intervals^∗ ⋮ Best fit bin packing with random order revisited ⋮ Random-order bin packing ⋮ Average case analysis of bounded space bin packing algorithms ⋮ A probabilistic analysis of a fixed partition policy for the inventory-routing problem ⋮ Inequalities for bin packing-III ⋮ Cutting stock problems with nondeterministic item lengths: a new approach to server consolidation ⋮ A new model for the linear 1-dimensional online clustering problem ⋮ Unnamed Item ⋮ Expected wasted space of optimal simple rectangle packing ⋮ An asymptotic 98.5\%-effective lower bound on fixed partition policies for the inventory-routing problem ⋮ Approximation of some NP-hard optimization problems by finite machines, in probability ⋮ Hoeffding's Inequality for Stopped Martingales and Semi-Markov Processes ⋮ Packing random intervals ⋮ A physicist's approach to number partitioning ⋮ A memetic algorithm approach for solving the multidimensional multi-way number partitioning problem ⋮ The ratio of the extreme to the sum in a random sequence ⋮ Proof of the local REM conjecture for number partitioning. I: Constant energy scales ⋮ Best Fit Bin Packing with Random Order Revisited ⋮ A note on packing random intervals with varying density ⋮ Partitioning under the \(L_p\) norm ⋮ Heuristics and exact methods for number partitioning ⋮ A tight upper bound for the \(k\)-partition problem on ideal sets ⋮ Multidimensional on-line bin-packing: An algorithm and its average-case analysis ⋮ Extending Graham's result on scheduling to other heuristics

This page was built for publication: