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

Abstract

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)

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, NOV 2018. (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, JUL 12 2019. (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, JUL 2019. (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, 2019. (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, FEB 2017. (15/11937-9, 14/19401-8, 13/08293-7, 16/14132-4, 13/01172-0, 14/20738-7)