Advanced search
Start date

One and two-dimensional bin packing with conflicts and unloading restrictions

Grant number: 16/14132-4
Support type:Scholarships in Brazil - Post-Doctorate
Effective date (Start): January 01, 2017
Effective date (End): January 28, 2018
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal researcher:Flávio Keidi Miyazawa
Grantee:Carla Negri Lintzmayer
Home Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil


This project aims to study and develop algorithms for packing problems. A classic example is the bin packing problem, for which the input is a list of items (each one with a size) and we want to pack them in the smallest number of bins (where the bins have a maximum size). Several of the simplest variations of packing problems belong to the class of NP-hard problems. In this project, we are interested in investigating variations of packing problems in one or two dimensions, which present restrictions of unloading or conflicts over the items of the input. For example, we can consider conflict restrictions when some items cannot be packed in the same bin or unloading restrictions when some packing order must be considered. Our goal is the theoretical study of some of these problems, with the development of algorithms for their open cases, emphasizing the study of approximation algorithms. (AU)

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items

Scientific publications (5)
(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)
YUCRA QUISPE, KENT E.; LINTZMAYER, CARLA N.; XAVIER, EDUARDO C.. An exact algorithm for the Blocks Relocation Problem with new lower bounds. Computers & Operations Research, v. 99, p. 206-217, . (16/14132-4, 15/11937-9, 16/23552-7)
LINTZMAYER, CARLA NEGRI; MIYAZAWA, FLAVIO KEIDI; XAVIER, EDUARDO CANDIDO. Online circle and sphere packing. THEORETICAL COMPUTER SCIENCE, v. 776, p. 75-94, . (16/23552-7, 16/14132-4, 15/11937-9, 16/01860-1)
SAMBINELLI, MAYCON; LINTZMAYER, CARLA NEGRI; DA SILVA, CANDIDA NUNES; LEE, ORLANDO. Berge's Conjecture and Aharoni-Hartman-Hoffman's Conjecture for Locally In-Semicomplete Digraphs. GRAPHS AND COMBINATORICS, v. 35, n. 4, p. 921-931, . (16/14132-4, 15/11937-9)
SANTOS MIRANDA, GUILHERME HENRIQUE; LINTZMAYER, CARLA NEGRI; DIAS, ZANONI. Sorting Permutations by lambda-Operations. JOURNAL OF UNIVERSAL COMPUTER SCIENCE, v. 25, n. 2, p. 98-121, . (17/12646-3, 13/08293-7, 15/11937-9, 16/14132-4)
LINTZMAYER, CARLA NEGRI; FERTIN, GUILLAUME; DIAS, ZANONI. Sorting permutations by prefix and suffix rearrangements. JOURNAL OF BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, v. 15, n. 1, . (15/11937-9, 14/19401-8, 13/08293-7, 16/14132-4, 13/01172-0, 14/20738-7)

Please report errors in scientific publications list by writing to: