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

• Grant number: 16/14132-4
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• Start date: January 01, 2017
• End date: January 28, 2018
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Flávio Keidi Miyazawa
• Grantee: Carla Negri Lintzmayer
• Host 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

(8)

(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)

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. (13/08293-7, 14/20738-7, 15/11937-9, 14/19401-8, 16/14132-4, 13/01172-0)

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)

SANTOS MIRANDA, GUILHERME HENRIQUE; LINTZMAYER, CARLA NEGRI; DIAS, ZANONI; JANSSON, J; MARTINVIDE, C; VEGARODRIGUEZ, MA. Sorting Permutations by Limited-Size Operations. ALGORITHMS FOR COMPUTATIONAL BIOLOGY (ALCOB 2018), v. 10849, p. 12-pg., 2018-01-01. (13/08293-7, 17/12646-3, 15/11937-9, 16/14132-4)

ALEXANDRINO, ALEXSANDRO OLIVEIRA; LINTZMAYER, CARLA NEGRI; DIAS, ZANONI; JANSSON, J; MARTINVIDE, C; VEGARODRIGUEZ, MA. Approximation Algorithms for Sorting Permutations by Fragmentation-Weighted Operations. ALGORITHMS FOR COMPUTATIONAL BIOLOGY (ALCOB 2018), v. 10849, p. 12-pg., 2018-01-01. (17/12646-3, 16/14132-4, 15/11937-9, 13/08293-7, 17/16871-1)

LINTZMAYER, CARLA NEGRI; MIYAZAWA, FLAVIO KEIDI; XAVIER, EDUARDO CANDIDO; BENDER, MA; FARACHCOLTON, M; MOSTEIRO, MA. Two-Dimensional Knapsack for Circles. LATIN 2018: THEORETICAL INFORMATICS, v. 10807, p. 14-pg., 2018-01-01. (15/11937-9, 16/14132-4, 16/23552-7, 16/01860-1)

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)

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/23552-7, 16/14132-4, 15/11937-9)