Empacotamentos uni e bidimensionais com restrições de conflitos e remoções

• Processo: 16/14132-4
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Data de Início da vigência: 01 de janeiro de 2017
• Data de Término da vigência: 28 de janeiro de 2018
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Flávio Keidi Miyazawa
• Beneficiário: Carla Negri Lintzmayer
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Algoritmos de aproximação Problemas de corte e empacotamento
• Palavra(s)-Chave do Pesquisador: Algoritmos de Aproximação | bin packing problem | Conflitos | Problemas de Empacotamento | restrições de remoção | Algoritmos de Aproximação

Resumo

Este projeto visa o estudo e desenvolvimento de algoritmos para problemas de empacotamento. Um exemplo clássico desse tipo de problema é o problema de empacotamento em recipientes, que tem como entrada uma lista de itens (cada um com um tamanho) e deseja-se empacotá-los no menor número de recipientes (tendo os recipientes um tamanho máximo). Muitas das variações mais simples de problemas de empacotamento se encaixam na classe de problemas NP-difícil. Neste projeto, estamos interessados em investigar variações uni ou bidimensionais de problemas de empacotamentos que apresentam restrições de remoção ou conflitos nos itens da entrada. Por exemplo, considerar restrições de conflito onde alguns itens da entrada não podem ser empacotados no mesmo recipiente, ou restrições de remoção quando alguma ordem de empacotamento deve ser respeitada. Nosso objetivo é o estudo teórico de alguns desses problemas, com o desenvolvimento de algoritmos para casos em aberto dos mesmos, dando ênfase ao estudo de algoritmos aproximados. (AU)

Publicações científicas

(8)

(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)

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)