Lehilton Lelis Chaves Pedrosa

I am an associate professor at IC.

Institute of Computing
Campinas State University
Av. Albert Einstein, 1251, room 12
13083-852, Campinas-SP
Brazil

lehilton@ic.unicamp.br

short bio

I graduated at the University of Brasilia, 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

Lattes Curriculum

Teaching, Publications, Students, DBLP, LOCO, Exact Course

Information pear interested in guidance

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

• Complexity of Algorithms I

previous semesters

• Approximation Algorithms (2s2019, 2s2022)
• Parameterized Algorithms (2s2016, 2s2018, 2s2021)
• Complexity of Algorithms I (1s2017, 1s2020)
• Algorithms and Computer Programming (1s2016, 1s2020, 1s2021, 1s2022)
• Data Structures (2s2015🇧🇷 2s2020, 2s2021, 2s2022)
• Algorithm Design and Analysis I (2s2017)
• Algorithm Design and Analysis II (1s2017, 1s2018)

List of publications

Published articles

preprints

• Yulle GF Borges, Vinícius L. de Lima, Flávio K. Miyazawa, Lehilton LC Pedrosa, Thiago A. de Queiroz, Rafael CS Schouery. Algorithms for the Bin Packing Problem with Scenarios. Arxiv

• Mauro RC Silva; Lehilton LC Pedrosa; Rafael CS Schouery. Approximation algorithms for the MAXSPACE advertisement problem. Arxiv

textbook chapter

• Flavio K. Miyazawa; Lehilton LC Pedrosa. Approximation algorithms. In: Ana Flávia U. Macambira; Luidi Simonetti; Rosiane F. Rodrigues; Nelson Maculan (Org.). Topics in Integer Optimization. UFRJ publisher, 2021. eBook (only in Dutch at the moment)

Published articles

• Lehilton LC Pedrosa; Marcelo PL Benedito; Hugo KK Rosado. On the Complexity of the Cable-Trench. Discrete Applied Mathematics (online first).

• Lehilton LC Pedrosa; Hugo KK Pink. A 2-approximation for the k-prize-collecting Steiner tree problem. Algorithmic (online first). Arxiv

• Michael Á. M. alarcon; Lehilton LC 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 LC Pedrosa; Rafael CS Schouery; Uéverton S. Souza. Computing the Largest Bond and the Maximum Connected Cut of a Graph. Algorithmic v. 83, pp. 1421–1458, 2021. Arxiv

• Marcelo PL Benedito; Lehilton LC Pedrosa. Approximation algorithms for Median Hub Location Problems. Journal of Combinatorial Optimization, vol. 38, pp. 375-401, 2019.

• Lehilton LC Pedrosa; Maxim Sviridenko. Integrated Supply Chain Management via Randomized Rounding. INFORMS Journal On Computing, vol. 30, pp. 124-136, 2018.

• Lehilton LC Pedrosa; Rafael CS Schouery. Approximation algorithms for the bus evacuation problem. Journal of Combinatorial Optimization, vol. 36, pp. 131-141, 2018.

• Flavio K. Miyazawa; Lehilton LC Pedrosa; Rafael CS Schouery; Renata GD Souza. PTAS for the Geometric Connected Facility Location Problem. Theory of Computing Systems, vol. 61, pp. 871–892, 2017.

• Cristina G. Fernandes; Samuel P. Paula; Lehilton LC Pedrosa. Improved Approximation Algorithms for Capacitated Fault-Tolerant k-Center. Algorithmics, s. 80, pp. 1041-1072, 2017. Arxiv

• Lehilton LC Pedrosa. A Brief Introduction to Approximation Algorithms. Operational research for development, v. 9, pp. 109-118, 2017.

• Flavio K. Miyazawa; Lehilton LC Pedrosa; Rafael CS Schouery; Maxim Sviridenko; Yoshiko Wakabayashi. Polynomial-Time Approximation Schemes for Circle and Other Packaging Problems. Algorithmics, s. 76, pp. 536-568, 2016. Arxiv

• Luis AA Meira; Flavio K. Miyazawa; Lehilton LC Pedrosa. Clustering through Continuous Facility Location Problems. Theoretical Computer Science, vol. 657, p. 137–145, 2016.

• Lucas P. Melo; Flavio K. Miyazawa; Lehilton LC Pedrosa; Rafael CS Schouery. Approximation algorithms for k-level stochastic facility location problems. Journal of Combinatorial Optimization, vol. 34, pp. 266-278, 2016.

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

• Lehilton LC 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 RC Silva, Rafael CS Schouery, Lehilton LC 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 LC 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 PL Benedito; Lucas P. Melo; Lehilton LC Pedrosa. A parameterized approximation algorithm for the Multiple Allocation k-Hub Center. In: Theoretical Informatics: 15th Latin American Symposium (LATIN) (to appear), 2022.

• Marcelo PL Benedito; Lehilton LC Pedrosa; Hugo KK Pink. 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 PL Benedito; Lehilton LC 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 LC Pedrosa; Hugo KK Pink. 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 LC Pedrosa; Greis YO 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 LC Pedrosa; Rafael CS 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 LC Pedrosa; Greis YO Quesquen; Rafael CS Schouery. An Asymptotically Optimal Approximation Algorithm for the Traveling Car Renter Problem. In: Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS), Schloss Dagstuhl, pp. 14:1–14:15 2019.

• Mauro RC Silva; Rafael CS Schouery; Lehilton LC Pedrosa. A polynomial-time approximation 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 LC 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 LC Pedrosa. Improved Approximation Algorithms for Capacitated Fault-Tolerant k-Center. In: Theoretical Informatics: 12th Latin American Symposium (LATIN), Springer, pp. 441–453, 2016.

• Flavio K. Miyazawa; Lehilton LC Pedrosa; Rafael CS Schouery; Maxim Sviridenko; Yoshiko Wakabayashi. Polynomial-Time Approximation Schemes for Circle Packing Problems. In: 22nd Annual European Symposium on Algorithms (ESA), Springer, pp. 713–724, 2014.

• Lehilton LC 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 AA Meira; Flavio K. Miyazawa; Lehilton LC 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 LC 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 LC 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 LC Pedrosa. [PL Rounding to the Balanced Facility Location Problem](PL Rounding to the Balanced Facility Location Problem). In: 8th Computing Theory Meeting (ETC), SBC, pp. 129-132, 2023.

• Lehilton LC Pedrosa; Lucas de O. Silva. Freeze-Tag Remains NP-hard on Binary and Ternary Trees. In: 8th Computing Theory Meeting (ETC), SBC, pp. 94-98, 2023.

• Lehilton LC Pedrosa; Mauro RC Silva; Rafael CS Schouery. Complexity of the Positional Knapsack Problem. In: 7th Computing Theory Meeting (ETC), SBC, pp. 53-56, 2022.

• Michael Á. M. Alarcon; Lehilton LC Pedrosa. An Approach to the Resupply Problem in Conjunction with Capabilities. In: 6th Meeting on Theory of Computation (ETC), SBC, pp. 1-4, 2021.

• Celso A. Weffort-Santos; Lehilton LC Pedrosa. (Star,k)-colourings of graphs with bounded treewidth. In: 5th Meeting on Theory of Computation (ETC), SBC, pp. 1-4, 2020.

• Marcelo PL Benedito; Lehilton LC Pedrosa; Hugo KK Pink. A Constant-Factor Approximation for the Generalized Cable-Trench Problem. In: 4th Meeting on Theory of Computation (ETC), SBC, pp. 1-4, 2019.

• Yulle GF Borges; Thiago A. Queiroz; Vinícius L. Lima; Flavio K. Miyazawa; Lehilton LC Pedrosa. An approximation scheme for a packaging problem with scenarios. In: 4th Meeting on Theory of Computation (ETC), SBC, pp. 1-4, 2019.

• Lehilton LC Pedrosa; Rafael CS Schouery. An Optimal Approach to the Rental Clerk Problem. In: 3th Meeting on Theory of Computation (ETC), SBC, pp. 93-96, 2018.

• Lehilton LC Pedrosa; Vinícius B. Souza. An Approach to the Capable Terminal Allocation Problem. In: 2th Meeting on Theory of Computation (ETC), SBC, pp. 47-50, 2017.

• Lehilton LC Pedrosa; Rafael CS Schouery. Approach Algorithm for the Bus Evacuation Problem. In: 2th Meeting on Theory of Computation (ETC), SBC, pp. 131-134, 2017.

• Lehilton LC Pedrosa. A Primal-Dual Approximation Algorithm for the One-Warehouse Multiple-Retailer Problem. In: XLVIII Brazilian Symposium on Operations Research (SBPO), SOBRAPO, pp. 2364–2374, 2016.

• Lehilton LC Pedrosa; Vinícius F. Santos; Rafael CS Schouery. An Approach to the Terminal Allocation Problem. In: 1th Meeting on Theory of Computation (ETC), SBC, pp. 824-827, 2016.

dissertations

• Approximation Algorithms for Facility Allocation Problems and Other Supply Chain Problems. Doctorate dissertation. State University of Campinas, 2014.

• Automatic Generation of Test Cases for Finite State Machines. Master's thesis. State University of Campinas, 2010.

• L-systems as a modeling tool. Undergraduate monograph. University of Brasilia, 2007.

Technical reports

• Lehilton LC Pedrosa; Arnaldo V. Moura. Testing Combined Finite State Machines🇧🇷 Technical report. 2010.

• Lehilton LC Pedrosa; José CL Ralha. L-systems and the halting problem🇧🇷 Technical report. 2008.

current students

PhD students

• Gray Yvet Oropeza Quesquén
• Miguel Angel Marfurt Alarcon
• Samuel Plaça de Paula
• Mauro Roberto Costa da Silva (co-supervisor)

Master's students

• William Porto Londe
• Lucas De OliveiraSilva

graduate students

PhD students

• Marcelo Pinheiro Benedito [thesis to be published]

• Hugo Kooki Kasuya Rosado (thesis)

Master's students

• Gray Yvet Oropeza Quesquén (dissertation)
• Hugo Kooki Kasuya Rosado (dissertation)
• Lucas Prado Melo (dissertation)
• Marcelo Pinheiro Benedito (dissertation)
• Miguel Angel Marfurt Alarcon (dissertation
• Mauro Roberto Costa da Silva (co-supervisor, dissertation)