Lehilton Lelis Chaves Pedrosa

I am an associate professor at IC.

Instituto de Computação
Universidade Estadual de Campinas
Av. Albert Einstein, 1251, sala 12
13083-852, Campinas-SP
Brazil

lehilton@ic.unicamp.br

Short bio

I graduated at the University of Brasília, and obtained Masters and PhD degrees at the Institute of Computing (IC) of the University of Campinas in 2014. I was a visitor researcher at DIMAP, in the University of Warwick in 2013, and worked as a post-doc at the Institute of Mathematics and Statistics of the University of São Paulo in 2015.

Shortcuts

Curriculum Lattes

Teaching, Publications, Students, DBLP, LOCo, Curso Exato

Informação pera interessados em orientação

Research interests

• Design and Analysis of Algorithms
• Combinatorial Optimization
• Approximation Algorithms
• Parameterized Algorithms
• Operations Research
• Graph Theory

Other interests

• Automata and formal languages
• Free media: webradio stream etc.

Teaching

• Estruturas de Dados

Previous semesters

• Algoritmos de Aproximação (2s2019, 2s2022)
• Algoritmos Parametrizados (2s2016, 2s2018, 2s2021)
• Complexidade de Algoritmos I (1s2017, 1s2020, 1s2020)
• Algoritmos e Programação de Computadores (1s2016, 1s2020, 1s2021, 1s2022)
• Estruturas de Dados (2s2015, …, 2s2020, 2s2021, 2s2022)
• Projeto e Análise de Algoritmos I (2s2017)
• Projeto e Análise de Algoritmos II (1s2017, 1s2018)

List of publications

Published articles

Preprints

• Mauro R. C. Silva; Lehilton L. C. Pedrosa; Rafael C. S. Schouery. Approximation algorithms for the MAXSPACE advertisement problem. Arxiv

Textbook chapter

• Flávio K. Miyazawa; Lehilton L. C. Pedrosa. Algoritmos de aproximação. In: Ana Flávia U. Macambira; Luidi Simonetti; Rosiane F. Rodrigues; Nelson Maculan (Org.). Tópicos em Otimização Inteira. Editora UFRJ, 2021. e-book

Published articles

• Yulle G. F. Borges, Vinícius L. de Lima, Flávio K. Miyazawa, Lehilton L. C. Pedrosa, Thiago A. de Queiroz, Rafael C. S. Schouery. Algorithms for the Bin Packing Problem with Scenarios. Journal of Combinatorial Optimization v. 48, pp.~1–28, 2024. Arxiv

• Lehilton L. C. Pedrosa; Marcelo P. L. Benedito; Hugo K. K. Rosado. On the Complexity of the Cable-Trench. Discrete Applied Mathematics (online first).

• Lehilton L. C. Pedrosa; Hugo K. K. Rosado. A 2-approximation for the k-prize-collecting Steiner tree problem. Algorithmica (online first). Arxiv

• Miguel Á. M. alarcón; Lehilton L. C. Pedrosa. Improved approximation for the capacitated inventory access point problem. Operations Research Letters. v. 49, pp. 874–876, 2021.

• Gabriel L. Duarte; Hiroshi Eto; Tesshu Hanaka; Yasuaki Kobayashi; Yusuke Kobayashi; Daniel Lokshtanov; Lehilton L. C. Pedrosa; Rafael C. S. Schouery; Uéverton S. Souza. Computing the Largest Bond and the Maximum Connected Cut of a Graph. Algorithmica v. 83, pp. 1421–1458, 2021. Arxiv

• Marcelo P. L. Benedito; Lehilton L. C. Pedrosa. Approximation algorithms for Median Hub Location Problems. Journal of Combinatorial Optimization, v. 38, pp. 375–401, 2019.

• Lehilton L. C. Pedrosa; Maxim Sviridenko. Integrated Supply Chain Management via Randomized Rounding. INFORMS Journal On Computing, v. 30, pp. 124–136, 2018.

• Lehilton L. C. Pedrosa; Rafael C. S. Schouery. Approximation algorithms for the bus evacuation problem. Journal of Combinatorial Optimization, v. 36, pp. 131–141, 2018.

• Flávio K. Miyazawa; Lehilton L. C. Pedrosa; Rafael C. S. Schouery; Renata G. D. Souza. A PTAS for the Geometric Connected Facility Location Problem. Theory of Computing Systems, v. 61, pp. 871–892, 2017.

• Cristina G. Fernandes; Samuel P. Paula; Lehilton L. C. Pedrosa. Improved Approximation Algorithms for Capacitated Fault-Tolerant k-Center. Algorithmica, v. 80, pp. 1041–1072, 2017. Arxiv

• Lehilton L. C. Pedrosa. Uma Breve Introdução a Algoritmos de Aproximação. Pesquisa operacional para o desenvolvimento, v. 9, pp. 109–118, 2017.

• Flávio K. Miyazawa; Lehilton L. C. Pedrosa; Rafael C. S. Schouery; Maxim Sviridenko; Yoshiko Wakabayashi. Polynomial-Time Approximation Schemes for Circle and Other Packing Problems. Algorithmica, v. 76, pp. 536–568, 2016. Arxiv

• Luis A. A. Meira; Flávio K. Miyazawa; Lehilton L. C. Pedrosa. Clustering through Continuous Facility Location Problems. Theoretical Computer Science, v. 657, pp. 137–145, 2016.

• Lucas P. Melo; Flávio K. Miyazawa; Lehilton L. C. Pedrosa; Rafael C. S. Schouery. Approximation algorithms for k-level stochastic facility location problems. Journal of Combinatorial Optimization, v. 34, pp. 266–278, 2016.

• Cristina G. Fernandes; Luis A. A. Meira; Flávio K. Miyazawa; Lehilton L. C. Pedrosa. A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems. Mathematical Programming, v. 153, pp. 655–685, 2015. Arxiv

• Lehilton L. C. Pedrosa; Arnaldo V. Moura. Incremental testing of finite state machines. Software Testing Verification and Reliability, v. 23, pp. 585–612, 2013.

Papers in conference proceedings

• Mauro R. C. Silva, Rafael C. S. Schouery, Lehilton L. C. Pedrosa. [A Polynomial-time Approximation Scheme for the MAXSPACE Advertisement Problem (Brief Announcement)]. In XII Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS 2023), to appear, 2023.

• Lehilton L. C. Pedrosa; Lucas de O. Silva. [Freeze-Tag is NP-hard in 3D with L₁-distance]. In: XII Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS), 2023 (to appear)

• Marcelo P. L. Benedito; Lucas P. Melo; Lehilton L. C. Pedrosa. A parameterized approximation algorithm for the Multiple Allocation k-Hub Center. In: Theoretical Informatics: 15th Latin American Symposium (LATIN) (to appear), 2022.

• Marcelo P. L. Benedito; Lehilton L. C. Pedrosa; Hugo K. K. Rosado. On the Inapproximability of the Cable-Trench Problem. In: XI Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS), Elsevier, pp. 39–48, 2021.

• Marcelo P. L. Benedito; Lehilton L. C. Pedrosa. An efficient parameterized approximation scheme for the Star k-Hub Center. In: XI Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS), Elsevier, pp. 49–58, 2021.

• Lehilton L. C. Pedrosa; Hugo K. K. Rosado. A 2-approximation for the k-prize-collecting Steiner tree problem. In: Theoretical Informatics: 14th Latin American Symposium (LATIN), Springer, pp. 76–88, 2020.

• Lehilton L. C. Pedrosa; Greis Y. O. Quesquen. Approximating Routing and Connectivity Problems with Multiple Distances. In: Theoretical Informatics: 14th Latin American Symposium (LATIN), Springer, pp. 63–75, 2020.

• Gabriel L. Duarte; Daniel Lokshtanov; Lehilton L. C. Pedrosa; Rafael C. S. Schouery; Uéverton S. Souza. Computing the largest bond of a graph. In: 14th International Symposium on Parameterized and Exact Computation (IPEC), Schloss Dagstuhl, pp. 12:1–12:15, 2019. Arxiv

• Lehilton L. C. Pedrosa; Greis Y. O. Quesquen; Rafael C. S. Schouery. An Asymptotically Optimal Approximation Algorithm for the Travelling Car Renter Problem. In: Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS), Schloss Dagstuhl, pp. 14:1–14:15 2019.

• Mauro R. C. Silva; Rafael C. S. Schouery; Lehilton L. C. Pedrosa. A polynomial-time aproximation scheme for the MAXSPACE advertisement problem. In: Tenth Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS), Elsevier, pp. 699–710, 2019

• Allan M. de Souza; Lehilton L. C. Pedrosa; Leonardo C. Botega; Leandro Villas. Itssafe: An Intelligent Transportation System for Improving Safety and Traffic Efficiency. In: 87th Vehicular Technology Conference (VTC), IEEE, pp. 1–7, 2018.

• Cristina G. Fernandes; Samuel P. de Paula; Lehilton L. C. Pedrosa. Improved Approximation Algorithms for Capacitated Fault-Tolerant k-Center. In: Theoretical Informatics: 12th Latin American Symposium (LATIN), Springer, pp. 441–453, 2016.

• Flávio K. Miyazawa; Lehilton L. C. Pedrosa; Rafael C. S. Schouery; Maxim Sviridenko; Yoshiko Wakabayashi. Polynomial-Time Approximation Schemes for Circle Packing Problems. In: 22th Annual European Symposium on Algorithms (ESA), Springer, pp. 713–724, 2014.

• Lehilton L. C. Pedrosa; Maxim Sviridenko. Integrated Supply Chain Management via Randomized Rounding. In: Theoretical Informatics: 11th Latin American Symposium (LATIN), Springer, pp. 562–573, 2014.

• Cristina G. Fernandes; Luis A. A. Meira; Flávio K. Miyazawa; Lehilton L. C. Pedrosa. A Systematic Approach to Bound Factor Revealing LPs and Its Application to the Metric and Squared Metric Facility Location Problems. In: 15th International Workshop Approximation, Randomization, and Combinatorial Optimization (APPROX-RANDOM), Springer, pp. 146–157, 2012.

• Lehilton L. C. Pedrosa; Arnaldo V. Moura. Generalized Partial Test Case Generation Method. In: 4th Secure Software Integration and Reliability Improvement (SSIRI), IEEE, pp. 70–77, 2010.

• Lehilton L. C. Pedrosa; Arnaldo V. Moura. A New Method for Incremental Testing of Finite State Machines. In: Second NASA Formal Methods Symposium (NFM), NASA Langley Research Center, pp. 109–118, 2010.

Extended abstracts in conference proceedings

• Lehilton L. C. Pedrosa. [Arredondamento de PL para o Problema de Localização de Instalações Balanceado](Arredondamento de PL para o Problema de Localização de Instalações Balanceado). In: 8º Encontro de Teoria de Computação (ETC), SBC, pp. 129-132, 2023.

• Lehilton L. C. Pedrosa; Lucas de O. Silva. Freeze-Tag Remains NP-hard on Binary and Ternary Trees. In: 8º Encontro de Teoria de Computação (ETC), SBC, pp. 94-98, 2023.

• Lehilton L. C. Pedrosa; Mauro R. C. Silva; Rafael C. S. Schouery. Complexidade do Positional Knapsack Problem. In: 7º Encontro de Teoria de Computação (ETC), SBC, pp. 53-56, 2022.

• Miguel Á. M. Alarcon; Lehilton L. C. Pedrosa. Uma aproximação para o Problema de Reabastecimento em Conjunto com Capacidades. In: 6º Encontro de Teoria de Computação (ETC), SBC, pp. 1–4, 2021.

• Celso A. Weffort-Santos; Lehilton L. C. Pedrosa. (Star, k)-colourings of graphs with bounded treewidth. In: 5º Encontro de Teoria de Computação (ETC), SBC, pp. 1–4, 2020.

• Marcelo P. L. Benedito; Lehilton L. C. Pedrosa; Hugo K. K. Rosado. A Constant-Factor Approximation for the Generalized Cable-Trench Problem. In: 4º Encontro de Teoria da Computação (ETC), SBC, pp. 1–4, 2019.

• Yulle G. F. Borges; Thiago A. Queiroz; Vinícius L. Lima; Flávio K. Miyazawa; Lehilton L. C. Pedrosa. Um esquema de aproximação para um problema de empacotamento com cenários. In: 4º Encontro de Teoria da Computação (ETC), SBC, pp. 1–4, 2019.

• Lehilton L. C. Pedrosa; Rafael C. S. Schouery. Uma Aproximação Ótima para o Problema do Caixeiro Alugador. In: 3º Encontro de Teoria da Computação (ETC), SBC, pp. 93–96, 2018.

• Lehilton L. C. Pedrosa; Vinícius B. Souza. Uma Aproximação para o Problema de Alocação de Terminais com Capacidade. In: 2º Encontro de Teoria da Computação (ETC), SBC, pp. 47–50, 2017.

• Lehilton L. C. Pedrosa; Rafael C. S. Schouery. Algoritmo de Aproximação para o Problema da Evacuação por Ônibus. In: 2º Encontro de Teoria da Computação (ETC), SBC, pp. 131–134, 2017.

• Lehilton L. C. Pedrosa. A Primal-Dual Approximation Algorithm for the One-Warehouse Multiple-Retailer Problem. In: XLVIII Simpósio Brasileiro de Pesquisa Operacional (SBPO), SOBRAPO, pp. 2364–2374, 2016.

• Lehilton L. C. Pedrosa; Vinícius F. Santos; Rafael C. S. Schouery. Uma Aproximação para o Problema de Alocação de Terminais. In: 1º Encontro de Teoria da Computação (ETC), SBC, pp. 824–827, 2016.

Dissertations

• Algoritmos de Aproximação para Problemas de Alocação de Instalações e Outros Problemas de Cadeia de Fornecimento. Doctorate dissertation. Universidade Estadual de Campinas, 2014.

• Geração Automática de Casos de Testes para Máquinas de Estados Finitos. Master’s thesis. Universidade Estadual de Campinas, 2010.

• L-systems como instrumento de modelagem. Undergraduate monography. Universidade de Brasília, 2007.

Technical reports

• Lehilton L. C. Pedrosa; Arnaldo V. Moura. Testing Combined Finite State Machines. Technical report. 2010.

• Lehilton L. C. Pedrosa; José C. L. Ralha. L-systems e o problema da parada. Technical report. 2008.

Current students

PhD students

• Greis Yvet Oropeza Quesquén
• Miguel Ángel Marfurt Alarcón
• Samuel Plaça de Paula
• Mauro Roberto Costa da Silva (co-supervisor)

Master’s students

• Guilherme Porto Londe
• Lucas De Oliveira Silva

Former students

PhD students

• Marcelo Pinheiro Benedito [tese a ser publicada]

• Hugo Kooki Kasuya Rosado (tese)

Master’s students

• Greis Yvet Oropeza Quesquén (dissertação)
• Hugo Kooki Kasuya Rosado (dissertação)
• Lucas Prado Melo (dissertação)
• Marcelo Pinheiro Benedito (dissertação)
• Miguel Ángel Marfurt Alarcón (dissertação
• Mauro Roberto Costa da Silva (co-supervisor, dissertação)