Approximation algorithms for a hierarchically structured bin packing problem

被引：11

作者：

Codenotti, B

De Marco, G

Leoncini, M

Montangero, M ^{[1
]}

Santini, M

机构：

[1] CNR, Ist Informat & Telemat, I-56100 Pisa, Italy

[2] Univ Modena, Dipartimento Sci Sociali Cognit & Quantitat, I-41100 Modena, Italy

[3] Univ Iowa, Dept Comp Sci, Iowa City, IA 52242 USA

来源：

INFORMATION PROCESSING LETTERS | 2004年 / 89卷 / 05期

关键词：

algorithms; approximation algorithms; bin packing; NP-hardness;

D O I：

10.1016/j.ipl.2003.12.001

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper we study a variant of the bin packing problem in which the items to be packed are structured as the leaves of a tree. The problem is motivated by document organization and retrieval. We show that the problem is NP-hard and we give approximation algorithms for the general case and for the particular case in which all the items have the same size. (C) 2003 Elsevier B.V. All rights reserved.

引用

页码：215 / 221

页数：7

共 10 条

[1]

Carey M., 1979, COMPUTER INTRACTABIL

[2] Scalable feature selection, classification and signature generation for organizing large text databases into hierarchical topic taxonomies [J].

Chakrabarti, S ;

Dom, B ;

Agrawal, R ;

Raghavan, P .

VLDB JOURNAL, 1998, 7 (03) :163-178

[3]

Co man Jr EG, 1996, APPROXIMATION ALGORI, P46

[4]

Crescenzi P., A Compendium of NP Optimization Problems

[5]

Dhillon IS, 2001, MASSIVE COMP, V2, P357

[6]

FLAKE GW, 2002, 200206 NEC

[7]

KARMARKAR N, 1982, P 23 ANN S FDN COMP, P312

[8]

SIMCHILEVI D, 1994, NAV RES LOG, V41, P579, DOI 10.1002/1520-6750(199406)41:4<579::AID-NAV3220410409>3.0.CO

[9]

2-G

[10]

VILES CL, 1995, P 18 ANN INT ACM SIG, P12

← 1 →