Advanced search
Start date
Betweenand

Investigation of hard problems from the algorithmic and structural stand points

Grant number: 15/11937-9
Support type:Research Projects - Thematic Grants
Duration: March 01, 2017 - February 28, 2023
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal researcher:Flávio Keidi Miyazawa
Grantee:Flávio Keidi Miyazawa
Home Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
Pesquisadores principais:
Eduardo Candido Xavier ; Orlando Lee ; Yoshiko Wakabayashi ; Zanoni Dias
Assoc. researchers:Fábio Luiz Usberti ; Lehilton Lelis Chaves Pedrosa ; Luis Augusto Angelotti Meira ; Rafael Crivellari Saliba Schouery ; Ulisses Martins Dias
Associated grant(s):19/12728-5 - The study of theoretical and practical combinatorial optimization problems applied on real scenarios, AV.EXT
Associated scholarship(s):22/06707-8 - Algorithms for packing problems, BP.PD
22/06728-5 - Algorithms for Packing Problems, BP.PD
21/13824-8 - Generalization of string partition problems, BP.DR
+ associated scholarships 21/12599-0 - Connectivity augmentation in graphs and robust networks, BP.MS
20/16439-5 - Fair maximum cover problems, BP.DR
21/06282-4 - Game Theory applied to resource allocation and pricing in Edge Computing, BP.MS
20/13162-2 - Packing problems with fixed number of bins, BP.DR
21/04409-7 - Algorithms for packing problems, BP.PD
20/11118-6 - Graph connectivity, BP.DR
20/06116-4 - chi-Diperfect Digraphs, BP.MS
20/06511-0 - Meta-heuristics for the colored bin packing problem, BP.IC
19/10400-2 - Approximation and parameterized algorithms for pair connectivity problems, BP.DR
19/14471-1 - Problems on spanners in graphs, BP.PD
19/27331-3 - Sorting by genome rearrangements problems, BP.PD
19/14492-9 - Algorithmic game theory applied to transportation problems, BP.IC
18/25950-5 - An algorithm for the electrical vehicle routin problem, BP.MS
17/26114-3 - Labelling Problems on Graphs, BP.PD
18/04679-1 - Conformal minors and Pfaffian orientations, BP.PD
18/00910-0 - Algorithms for Min-Max p-hub location problems and variants, BP.IC
17/23623-4 - Partition problems in graphs and digraphs, BP.PD
17/21297-2 - Advertisements scheduling problems, BP.MS
17/23343-1 - Exact algorithms and heuristics for Car-Sharing, BP.MS
17/11831-1 - Algorithms and models for cutting and packing problems, BP.DD
17/05223-9 - Game-theoretic analysis of transportation problems, BP.MS - associated scholarships

Abstract

The main theme of this project is the investigation of several problems on objects of discrete nature, with focus on their algorithmic, structural and theoretical aspects. We will give emphasis to the treatment of "hard problems" (formally known as NP-hard problems), but we will not restrict to this class of problems. We will also consider problems belonging to other complexity classes, as well as problems whose difficulty lies on the lack of information or on the decentralization of the decisions of different users, in contexts where the decision of an user affects the decision of the others. The algorithmic issues that will be investigated includes the design of efficient and practical algorithms (with performance guarantees, when possible), the development of new techniques, and the classification of several problems regarding their computational complexity. The structural and theoretical studies concerning the combinatorial objects that we will be carried out include their characterization, properties, conditions for their existence, counting and construction of these objects. The topics that we will investigate are interconnected and occur in several areas such as computational biology, discrete optimization, graph theory, logistics and economy. We expect that the research that will be conducted in this project will lead to relevant results, which will contribute to push forward the state of the art of the subject area. We also expect that this project will promote the academic formation of young researchers. Towards the end of the project, we envision an increase on the research activities in areas that are still little investigated in Brazil, but are intensively investigated in the main research centers abroad. (AU)

Articles published in Agência FAPESP Newsletter about the research grant:
Articles published in other media outlets (0 total):
More itemsLess items
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

Scientific publications (50)
(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)
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, . (13/03447-6, 16/23552-7, 16/01860-1, 15/11937-9)
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, . (16/23552-7, 14/02104-0, 15/11937-9)
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, . (13/03447-6, 15/11937-9, 13/21744-8)
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)
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)
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, . (17/16246-0, 15/11937-9, 17/12646-3)
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, . (18/16548-9, 18/16214-3, 17/16246-0, 15/11937-9, 18/05668-3, 13/08293-7, 17/12646-3, 17/16871-1)
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, . (15/11937-9, 15/04385-0, 14/14375-9)
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, . (15/11937-9, 16/23552-7, 19/12728-5, 16/01860-1, 18/19217-3)
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, . (13/08293-7, 15/11937-9, 19/27331-3, 17/12646-3)
GOMEZ, RENZO; WAKABAYASHI, YOSHIKO. Nontrivial path covers of graphs: existence, minimization and maximization. JOURNAL OF COMBINATORIAL OPTIMIZATION, v. 39, n. 2, p. 437-456, . (15/11937-9)
DE LIMA, MURILO SANTOS; SAN FELICE, MARIO CESAR; LEE, ORLANDO. Group parking permit problems. DISCRETE APPLIED MATHEMATICS, v. 281, n. SI, p. 172-194, . (14/18781-1, 15/11937-9, 17/11382-2)
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. 547-558, . (15/11937-9)
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, . (15/11937-9, 16/23552-7, 16/01860-1)
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, . (16/12006-1, 15/11937-9)
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, . (15/11937-9)
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, . (17/12646-3, 17/16246-0, 15/11937-9)
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, . (14/14375-9, 15/04385-0, 15/11937-9)
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, . (15/11937-9, 16/01860-1, 17/11831-1)
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, . (16/23552-7, 16/21250-3, 17/22611-2, 15/11937-9, 16/01860-1)
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, p. 1421-1458, . (15/11937-9)
DANTAS, ANA PAULA S.; DE SOUZA, CID C.; DIAS, ZANONI. A heuristic for the convex recoloring problem in graphs. International Transactions in Operational Research, v. 29, n. 3, p. 1454-1478, . (17/16246-0, 17/12646-3, 15/11937-9, 18/04760-3)
OLIVEIRA, ANDRE RODRIGUES; JEAN, GERALDINE; FERTIN, GUILLAUME; BRITO, KLAIRTON LIMA; DIAS, ULISSES; DIAS, ZANONI. orting Permutations by Intergenic Operation. IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, v. 18, n. 6, p. 2080-2093, . (19/27331-3, 13/08293-7, 17/12646-3, 15/11937-9)
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, . (13/08293-7, 15/11937-9, 17/16871-1, 17/12646-3, 17/16246-0)
LINTZMAYER, CARLA NEGRI; FERTIN, GUILLAUME; DIAS, ZANONI. Sorting permutations and binary strings by length-weighted rearrangements. THEORETICAL COMPUTER SCIENCE, v. 715, p. 35-59, . (14/20738-7, 14/19401-8, 13/01172-0, 15/11937-9, 13/08293-7)
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, . (17/12646-3, 17/16246-0, 13/08293-7, 15/11937-9)
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, . (17/16246-0, 17/12646-3, 15/11937-9, 13/08293-7)
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, . (16/23552-7, 15/11937-9)
OLIVEIRA, ANDRE R.; FERTIN, GUILLAUME; DIAS, ULISSES; DIAS, ZANONI. Sorting signed circular permutations by super short operations. Algorithms for Molecular Biology, v. 13, . (13/08293-7, 15/11937-9)
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, . (13/21744-8, 15/11937-9, 16/01860-1)
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)
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, . (15/11937-9)
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, . (14/19401-8, 13/08293-7, 15/11937-9)
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, . (17/23623-4, 13/03447-6, 15/11937-9)
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, . (14/50715-9, 16/50250-1, 17/16246-0, 17/20945-0, 14/12236-1, 13/50169-1, 15/11937-9, 17/12646-3, 13/50155-0, 15/24494-8)
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, . (17/16246-0, 19/27331-3, 15/11937-9, 17/12646-3)
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, . (17/12646-3, 15/11937-9, 13/08293-7, 19/27331-3)
MOURA, PHABLO F. S.; WAKABAYASHI, YOSHIKO. Strong intractability results for generalized convex recoloring problems. DISCRETE APPLIED MATHEMATICS, v. 281, n. SI, p. 252-260, . (16/21250-3, 17/22611-2, 15/11937-9)
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, . (14/25892-4, 15/11937-9, 16/23552-7, 16/01860-1)
BRITO, KLAIRTON L.; OLIVEIRA, ANDRE R.; ALEXANDRINO, ALEXSANDRO O.; DIAS, ULISSES; DIAS, ZANONI. An improved approximation algorithm for the reversal and transposition distance considering gene order and intergenic sizes. Algorithms for Molecular Biology, v. 16, n. 1, . (19/27331-3, 15/11937-9, 17/12646-3, 13/08293-7)
ALEXANDRINO, ALEXSANDRO OLIVEIRA; OLIVEIRA, ANDRE RODRIGUES; DIAS, ULISSES; DIAS, ZANONI. Incorporating intergenic regions into reversal and transposition distances with indels. JOURNAL OF BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, v. 19, n. 6, SI, . (19/27331-3, 17/12646-3, 13/08293-7, 15/11937-9)
GOMEZ, RENZO; WAKABAYASHI, YOSHIKO. Nontrivial path covers of graphs: existence, minimization and maximization. JOURNAL OF COMBINATORIAL OPTIMIZATION, . (15/11937-9)
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, . (16/23552-7, 13/21744-8, 15/11937-9, 16/01860-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, . (17/12646-3, 17/16871-1, 17/16246-0, 15/11937-9)
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, . (19/27331-3, 17/12646-3, 17/16246-0, 13/08293-7, 15/11937-9)
SIQUEIRA, GABRIEL; BRITO, KLAIRTON LIMA; DIAS, ULISSES; DIAS, ZANONI. euristics for Genome Rearrangement Distance With Replicated Gene. IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, v. 18, n. 6, p. 2094-2108, . (17/16246-0, 17/12646-3, 15/11937-9)
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, . (18/04876-1, 15/11937-9, 16/01860-1)
ALEXANDRINO, ALEXSANDRO OLIVEIRA; OLIVEIRA, ANDRE RODRIGUES; DIAS, ULISSES; DIAS, ZANONI. Labeled Cycle Graph for Transposition and Indel Distance. JOURNAL OF COMPUTATIONAL BIOLOGY, . (17/12646-3, 13/08293-7, 15/11937-9, 19/27331-3)

Please report errors in scientific publications list by writing to: cdi@fapesp.br.