✦ LIBER ✦

Tight complexity bounds for the two-dimensional real knapsack problem

✍ Scribed by Valentin E. Brimkov; Stefan S. Dantchev; Mauro Leoncini

Publisher: Springer Milan
Year: 1999
Tongue: English
Weight: 43 KB
Volume: 36
Category: Article
ISSN: 0008-0624
DOI: 10.1007/s100920050026

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

New pseudopolynomial complexity bounds f

New pseudopolynomial complexity bounds for the bounded and other integer Knapsack related problems

✍ Arie Tamir 📂 Article 📅 2009 🏛 Elsevier Science 🌐 English ⚖ 688 KB

An alternative to Ben-Or's lower bound f

An alternative to Ben-Or's lower bound for the knapsack problem complexity

✍ V.E. Brimkov; S.S. Dantchev 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 370 KB

Improved complexity bounds for location

Improved complexity bounds for location problems on the real line

✍ R. Hassin; A. Tamir 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 387 KB

Upper bounds for the homogeneous case of

Upper bounds for the homogeneous case of a two-dimensional packing problem

✍ H. Exeler 📂 Article 📅 1991 🏛 Springer 🌐 English ⚖ 520 KB

A branch-and-bound algorithm for the two

A branch-and-bound algorithm for the two-dimensional vector packing problem

✍ Frits C.R. Spieksma 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 661 KB

A new lower bound for the non-oriented t

A new lower bound for the non-oriented two-dimensional bin-packing problem

✍ François Clautiaux; Antoine Jouglet; Joseph El Hayek 📂 Article 📅 2007 🏛 Elsevier Science 🌐 English ⚖ 183 KB

We propose a new scheme for computing lower bounds for the non-oriented bin-packing problem when the bin is a square. It leads to bounds that theoretically dominate previous results. Computational experiments show that the bounds are tight. We also discuss the case where the bin is not a square.