Busca avançada
Ano de início
Entree

Investigação de problemas difíceis do ponto de vista algorítmico e estrutural

Processo: 15/11937-9
Linha de fomento:Auxílio à Pesquisa - Temático
Vigência: 01 de março de 2017 - 28 de fevereiro de 2023
Área do 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:Flávio Keidi Miyazawa
Instituição-sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
Pesquisadores principais:
Eduardo Candido Xavier ; Orlando Lee ; Yoshiko Wakabayashi ; Zanoni Dias
Pesq. associados:Fábio Luiz Usberti ; Lehilton Lelis Chaves Pedrosa ; Luis Augusto Angelotti Meira ; Rafael Crivellari Saliba Schouery ; Ulisses Martins Dias
Auxílios(s) vinculado(s):19/12728-5 - Estudo de problemas de otimização combinatória teóricos e aplicados em cenários reais, AV.EXT
Bolsa(s) vinculada(s):20/16439-5 - Problemas de coberturas justas e máximas, BP.DR
21/06282-4 - Teoria dos Jogos Algorítmica aplicada a alocação e precificação de recursos na Computação de Borda, BP.MS
20/13162-2 - Problemas de empacotamento com número fixo de recipientes, BP.DR
+ mais bolsas vinculadas 21/04409-7 - Algoritmos para problemas de empacotamento, BP.PD
20/11118-6 - Conexidade em grafos, BP.DR
20/06116-4 - Dígrafos chi-Diperfeitos, BP.MS
20/06511-0 - Meta-heurísticas para o problema de empacotamento colorido, BP.IC
19/10400-2 - Algoritmos de aproximação e parametrizados para problemas de conectividade de pares, BP.DR
19/14471-1 - Problemas sobre spanners em grafos, BP.PD
19/27331-3 - Problemas de ordenação por rearranjos de genomas, BP.PD
19/14492-9 - Aplicações de teoria dos jogos algoriítmica a problemas de transporte, BP.IC
18/25950-5 - Um algoritmo para o problema de roteirização de veículos elétricos, BP.MS
18/04679-1 - Menores conformes e orientações Pfaffianas, BP.PD
17/26114-3 - Problemas de Rotulação em Grafos, BP.PD
18/00910-0 - Algoritmos para problemas Min-Max de alocação de p-Terminais e variantes, BP.IC
17/23623-4 - Problemas de partição em grafos e dígrafos, BP.PD
17/21297-2 - Problemas de disposição de propagandas, BP.MS
17/23343-1 - Algoritmos exatos e heurísticas para o compartilhamento de veículos, BP.MS
17/11831-1 - Algoritmos e modelos para problemas de corte e empacotamento, BP.DD
17/05223-9 - Análise teórica de problemas de transporte sob a perspectiva da teoria dos jogos, BP.MS - menos bolsas vinculadas
Assunto(s):Biologia computacional  Otimização combinatória  Teoria dos grafos  Teoria dos jogos  Algoritmos 

Resumo

O tema central deste projeto é a investigação de diversos problemas sobre objetos de natureza discreta, tendo como foco o estudo de algoritmos e de questões estruturais e teóricas sobre esses objetos. Daremos ênfase ao tratamento de "problemas difíceis"(formalmente conhecidos como problemas NP-difíceis), mas não nos restringiremos a esta classe de problemas. Consideraremos também problemas pertencentes a outras classes de complexidade, bem como problemas onde a dificuldade de se resolvê-los eficientemente está na falta de informação ou mesmo na descentralização das decisões de diferentes usuários, em contextos onde a decisão de um usuário afeta a decisão dos demais. Os estudos de natureza algorítmica que serão contemplados incluem projetos de algoritmos eficientes e práticos (quando possível, com garantia de desempenho), desenvolvimento de novas técnicas, e classificação de diversos problemas com relação à sua pertinência a diferentes classes de complexidade computacional. As questões estruturais sobre os objetos combinatórios que investigaremos incluem sua caracterização, propriedades, condições para sua existência, quantificação e construção dos mesmos. Os tópicos e técnicas que investigaremos estão inter-relacionados e são aplicáveis a diversas áreas como biologia computacional, otimização discreta, teoria dos grafos, logística e economia. Esperamos que a execução deste projeto tenha como fruto a obtenção de resultados relevantes, que contribuam para o avanço do estado da arte da área de conhecimento em que se inserem. Também esperamos que este projeto contribua para a formação e qualificação de novos pesquisadores. Ao fim do projeto, também esperamos um aumento da pesquisa em áreas ainda pouco estudadas no Brasil, mas para as quais há intensa atividade nos principais centros de pesquisa no exterior. (AU)

Matéria(s) publicada(s) na Agência FAPESP sobre o auxílio:
Matéria(s) publicada(s) em Outras Mídias (0 total):
Mais itensMenos itens
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

Publicações científicas (47)
(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)
MARFURT ALARCON, MIGUEL ANGEL; CHAVES PEDROSA, LEHILTON LELIS. Improved approximation for the capacitated inventory access point problem. OPERATIONS RESEARCH LETTERS, v. 49, n. 6, p. 874-876, NOV 2021. Citações Web of Science: 0.
ALEXANDRINO, ALEXSANDRO OLIVEIRA; OLIVEIRA, ANDRE RODRIGUES; DIAS, ULISSES; DIAS, ZANONI. Labeled Cycle Graph for Transposition and Indel Distance. JOURNAL OF COMPUTATIONAL BIOLOGY, NOV 2021. Citações Web of Science: 0.
SIQUEIRA, GABRIEL; ALEXANDRINO, ALEXSANDRO OLIVEIRA; OLIVEIRA, ANDRE RODRIGUES; DIAS, ZANONI. Approximation algorithm for rearrangement distances considering repeated genes and intergenic regions. Algorithms for Molecular Biology, v. 16, n. 1 OCT 13 2021. Citações Web of Science: 0.
BRITO, KLAIRTON LIMA; ALEXANDRINO, ALEXSANDRO OLIVEIRA; OLIVEIRA, ANDRE RODRIGUES; DIAS, ULISSES; DIAS, ZANONI. Reversals and transpositions distance with proportion restriction. JOURNAL OF BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, v. 19, n. 4 AUG 2021. Citações Web of Science: 0.
RICHTER, R. BRUCE; SILVA, ANDRE C.; LEE, ORLANDO. Bounding the Number of Non-duplicates of the q-Side in Simple Drawings of K-p,K-q. GRAPHS AND COMBINATORICS, AUG 2021. Citações Web of Science: 0.
MIRANDA, GUILHERME HENRIQUE SANTOS; ALEXANDRINO, ALEXSANDRO OLIVEIRA; LINTZMAYER, CARLA NEGRI; DIAS, ZANONI. Approximation Algorithms for Sorting lambda-Permutations by lambda-Operations. ALGORITHMS, v. 14, n. 6 JUN 2021. Citações Web of Science: 0.
ALEXANDRINO, ALEXSANDRO OLIVEIRA; MIRANDA, GUILHERME HENRIQUE SANTOS; LINTZMAYER, CARLA NEGRI; DIAS, ZANONI. Length-weighted lambda-rearrangement distance. JOURNAL OF COMBINATORIAL OPTIMIZATION, v. 41, n. 3, p. 579-602, APR 2021. Citações Web of Science: 1.
ALEXANDRINO, ALEXSANDRO OLIVEIRA; OLIVEIRA, ANDRE RODRIGUES; DIAS, ULISSES; DIAS, ZANONI. Genome Rearrangement Distance with Reversals, Transpositions, and Indels. JOURNAL OF COMPUTATIONAL BIOLOGY, v. 28, n. 3, p. 235-247, MAR 1 2021. Citações Web of Science: 0.
IORI, MANUEL; DE LIMA, VINICIUS L.; MARTELLO, SILVANO; MIYAZAWA, FLAVIO K.; MONACI, MICHELE. Exact solution techniques for two-dimensional cutting and packing. European Journal of Operational Research, v. 289, n. 2, p. 399-415, MAR 1 2021. Citações Web of Science: 0.
DUARTE, GABRIEL L.; ETO, HIROSHI; HANAKA, TESSHU; KOBAYASHI, YASUAKI; KOBAYASHI, YUSUKE; LOKSHTANOV, DANIEL; PEDROSA, LEHILTON L. C.; SCHOUERY, RAFAEL C. S.; SOUZA, UEVERTON S. Computing the Largest Bond and the Maximum Connected Cut of a Graph. ALGORITHMICA, v. 83, n. 5 JAN 2021. Citações Web of Science: 0.
LILIANE DE AZEVEDO OLIVEIRA; VINÍCIUS LOTI DE LIMA; THIAGO ALVES DE QUEIROZ; FLÁVIO KEIDI MIYAZAWA. COMPARING A STATIC EQUILIBRIUM BASED METHOD WITH THE SUPPORT FACTOR FOR HORIZONTAL CARGO STABILITY IN THE CONTAINER LOADING PROBLEM. Pesquisa Operacional, v. 41, p. -, 2021.
KOHAYAKAWA, YOSHIHARU; MIYAZAWA, FLAVIO KEIDI; WAKABAYASHI, YOSHIKO. A tight lower bound for the online bounded space hypercube bin packing problem. DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, v. 23, n. 3 2021. Citações Web of Science: 0.
RODRIGUES, CAROLINE MAZINI; SORIANO-VARGAS, AUREA; LAVI, BAHRAM; ROCHA, ANDERSON; DIAS, ZANONI. Manifold Learning for Real-World Event Understanding. IEEE Transactions on Information Forensics and Security, v. 16, p. 2957-2972, 2021. Citações Web of Science: 0.
DANTAS, ANA PAULA S.; DE SOUZA, CID C.; DIAS, ZANONI. A heuristic for the convex recoloring problem in graphs. International Transactions in Operational Research, NOV 2020. Citações Web of Science: 0.
ALEXANDRINO, ALEXSANDRO OLIVEIRA; MIRANDA, GUILHERME HENRIQUE SANTOS; LINTZMAYER, CARLA NEGRI; DIAS, ZANONI. Length-weighted lambda-rearrangement distance. JOURNAL OF COMBINATORIAL OPTIMIZATION, v. 41, n. 3 NOV 2020. Citações Web of Science: 0.
LINTZMAYER, CARLA N.; MIYAZAWA, FLAVIO K.; MOURA, PHABLO F. S.; XAVIER, EDUARDO C. Randomized approximation scheme for Steiner Multi Cycle in the Euclidean plane. THEORETICAL COMPUTER SCIENCE, v. 835, p. 134-155, OCT 2 2020. Citações Web of Science: 0.
DE LIMA, MURILO SANTOS; SAN FELICE, MARIO CESAR; LEE, ORLANDO. Group parking permit problems. DISCRETE APPLIED MATHEMATICS, v. 281, n. SI, p. 172-194, JUL 15 2020. Citações Web of Science: 0.
MOURA, PHABLO F. S.; WAKABAYASHI, YOSHIKO. Strong intractability results for generalized convex recoloring problems. DISCRETE APPLIED MATHEMATICS, v. 281, n. SI, p. 252-260, JUL 15 2020. Citações Web of Science: 0.
BORGES, YULLE G. F.; MIYAZAWA, FLAVIO K.; SCHOUERY, RAFAEL C. S.; XAVIER, EDUARDO C. Exact algorithms for class-constrained packing problems. COMPUTERS & INDUSTRIAL ENGINEERING, v. 144, JUN 2020. Citações Web of Science: 1.
ALEXANDRINO, ALEXSANDRO OLIVEIRA; LINTZMAYER, CARLA NEGRI; DIAS, ZANONI. Sorting permutations by fragmentation-weighted operations. JOURNAL OF BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, v. 18, n. 2 APR 2020. Citações Web of Science: 0.
GOMEZ, RENZO; WAKABAYASHI, YOSHIKO. Nontrivial path covers of graphs: existence, minimization and maximization. JOURNAL OF COMBINATORIAL OPTIMIZATION, v. 39, n. 2, p. 437-456, FEB 2020. Citações Web of Science: 0.
ALEXANDRINO, ALEXSANDRO OLIVEIRA; OLIVEIRA, ANDRE RODRIGUES; DIAS, ULISSES; DIAS, ZANONI. On the Complexity of Some Variations of Sorting by Transpositions. JOURNAL OF UNIVERSAL COMPUTER SCIENCE, v. 26, n. 9, p. 1076-1094, 2020. Citações Web of Science: 0.
BRITO, KLAIRTON LIMA; JEAN, GERALDINE; FERTIN, GUILLAUME; OLIVEIRA, ANDRE RODRIGUES; DIAS, ULISSES; DIAS, ZANONI. Sorting by Genome Rearrangements on Both Gene Order and Intergenic Sizes. JOURNAL OF COMPUTATIONAL BIOLOGY, v. 27, n. 2 DEC 2019. Citações Web of Science: 0.
MUNOZ, JAVIER VARGAS; GONCALVES, MARCOS A.; DIAS, ZANONI; TORRES, RICARDO DA S. Hierarchical Clustering-Based Graphs for Large Scale Approximate Nearest Neighbor Search. PATTERN RECOGNITION, v. 96, DEC 2019. Citações Web of Science: 0.
OLIVEIRA, ANDRE R.; JEAN, GERALDINE; FERTIN, GUILLAUME; DIAS, ULISSES; DIAS, ZANONI. Super short operations on both gene order and intergenic sizes. Algorithms for Molecular Biology, v. 14, n. 1 NOV 5 2019. Citações Web of Science: 0.
OLIVEIRA, ANDRE RODRIGUES; BRITO, KLAIRTON LIMA; DIAS, ULISSES; DIAS, ZANONI. On the Complexity of Sorting by Reversals and Transpositions Problems. JOURNAL OF COMPUTATIONAL BIOLOGY, v. 26, n. 11, p. 1223-1229, NOV 1 2019. Citações Web of Science: 1.
BORGES, YULLE G. F.; SCHOUERY, RAFAEL C. S.; MIYAZAWA, FLAVIO K.; GRANELLI, FABRIZIO; DA FONSECA, NELSON L. S.; MELO, LUCAS P. Smart energy pricing for demand-side management in renewable energy smart grids. International Transactions in Operational Research, v. 27, n. 6 NOV 2019. Citações Web of Science: 0.
GOMEZ, RENZO; WAKABAYASHI, YOSHIKO. Nontrivial path covers of graphs: existence, minimization and maximization. JOURNAL OF COMBINATORIAL OPTIMIZATION, NOV 2019. Citações Web of Science: 0.
SILVA, ANDRE C.; ARROYO, ALAN; RICHTER, R. BRUCE; LEE, ORLANDO. Graphs with at most one crossing. DISCRETE MATHEMATICS, v. 342, n. 11, p. 3201-3207, NOV 2019. Citações Web of Science: 0.
BENEDITO, MARCELO P. L.; PEDROSA, LEHILTON L. C. Approximation algorithms for Median Hub Location Problems. JOURNAL OF COMBINATORIAL OPTIMIZATION, v. 38, n. 2, p. 375-401, AUG 2019. Citações Web of Science: 0.
BOTLER, FABIO; SAMBINELLI, MAYCON; COELHO, RAFAEL S.; LEE, ORLANDO. Gallai's path decomposition conjecture for graphs with treewidth at most 3. JOURNAL OF GRAPH THEORY, AUG 2019. Citações Web of Science: 0.
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. Citações Web of Science: 0.
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. Citações Web of Science: 0.
QUEIROZ, THIAGO A.; BRACHT, EVANDRO C.; MIYAZAWA, FLAVIO K.; BITTENCOURT, MARCO L. An extension of Queiroz and Miyazawa's method for vertical stability in two-dimensional packing problems to deal with horizontal stability. ENGINEERING OPTIMIZATION, v. 51, n. 6, p. 1049-1070, JUN 3 2019. Citações Web of Science: 1.
FERNANDES, CRISTINA G.; FERREIRA, CARLOS E.; MIYAZAWA, FLAVIO K.; WAKABAYASHI, YOSHIKO. Prices of Anarchy of Selfish 2D Bin Packing Games. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, v. 30, n. 3, p. 355-374, APR 2019. Citações Web of Science: 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. Citações Web of Science: 0.
FERNANDES, CRISTINA G.; SCHOUERY, RAFAEL C. S. Approximation Algorithms for the Max-Buying Problem with Limited Supply. ALGORITHMICA, v. 80, n. 11, p. 2973-2992, NOV 2018. Citações Web of Science: 0.
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. Citações Web of Science: 4.
POVOA, MARCELO G.; XAVIER, EDUARDO C. Approximation algorithms and heuristics for task scheduling in data-intensive distributed systems. International Transactions in Operational Research, v. 25, n. 5, p. 1417-1441, SEP 2018. Citações Web of Science: 0.
WAINER, JACQUES; XAVIER, EDUARDO C. A Controlled Experiment on Python vs C for an Introductory Programming Course: Student's Outcomes. ACM TRANSACTIONS ON COMPUTING EDUCATION, v. 18, n. 3 SEP 2018. Citações Web of Science: 0.
OLIVEIRA, ANDRE R.; FERTIN, GUILLAUME; DIAS, ULISSES; DIAS, ZANONI. Sorting signed circular permutations by super short operations. Algorithms for Molecular Biology, v. 13, JUL 26 2018. Citações Web of Science: 0.
PEDROSA, LEHILTON L. C.; SCHOUERY, RAFAEL C. S. Approximation algorithms for the bus evacuation problem. JOURNAL OF COMBINATORIAL OPTIMIZATION, v. 36, n. 1, p. 131-141, JUL 2018. Citações Web of Science: 0.
TICONA-ZEGARRA, EDSON; SCHOUERY, RAFAEL C. S.; VILLAS, LEANDRO A.; MIYAZAWA, FLAVIO K. Improved continuous enhancement routing solution for energy-aware data aggregation in wireless sensor networks. International Journal of Distributed Sensor Networks, v. 14, n. 5 MAY 11 2018. Citações Web of Science: 1.
LINTZMAYER, CARLA NEGRI; FERTIN, GUILLAUME; DIAS, ZANONI. Sorting permutations and binary strings by length-weighted rearrangements. THEORETICAL COMPUTER SCIENCE, v. 715, p. 35-59, MAR 8 2018. Citações Web of Science: 0.
C.H. SAMORA; F.L. USBERTI; C. LYRA. Relaxação Lagrangeana Aplicada ao Problema de Cobertura por Hubs. TEMA (São Carlos), v. 19, n. 3, p. -, Dez. 2018.
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. Citações Web of Science: 3.
OLIVEIRA, ANDRE RODRIGUES; DIAS, ULISSES; DIAS, ZANONI. On the Sorting by Reversals and Transpositions Problem. JOURNAL OF UNIVERSAL COMPUTER SCIENCE, v. 23, n. 9, p. 868-906, 2017. Citações Web of Science: 1.

Por favor, reporte erros na lista de publicações científicas escrevendo para: cdi@fapesp.br.