✦ LIBER ✦

Efficient Approximation Algorithms for Tiling and Packing Problems with Rectangles

✍ Scribed by Piotr Berman; Bhaskar DasGupta; S Muthukrishnan; Suneeta Ramaswami

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 202 KB
Volume: 41
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.2001.1188

No coin nor oath required. For personal study only.

✦ Synopsis

We provide improved approximation algorithms for several rectangle tiling and packing problems (RTILE, DRTILE, and d-RPACK) studied in the literature. Most of our algorithms are highly efficient since their running times are near-linear in the sparse input size rather than in the domain size. In addition, we improve the best known approximation ratios.

📜 SIMILAR VOLUMES

Constant Ratio Approximation Algorithms

Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem

✍ Daya Ram Gaur; Toshihide Ibaraki; Ramesh Krishnamurti 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 114 KB

We provide constant ratio approximation algorithms for two NP-hard problems, the rectangle stabbing problem and the rectilinear partitioning problem. In the rectangle stabbing problem, we are given a set of rectangles in two-dimensional space, with the objective of stabbing all rectangles with the m

Approximation algorithms for the capacit

Approximation algorithms for the capacitated traveling salesman problem with pickups and deliveries

✍ Shoshana Anily; Julien Bramel 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 100 KB 👁 2 views

We consider the Capacitated Traveling Salesman Problem with Pickups and Deliveries (CTSPPD). This problem is characterized by a set of n pickup points and a set of n delivery points. A single product is available at the pickup points which must be brought to the delivery points. A vehicle of limited