Mauro Roberto Costa da Silva

dblp:390/8654 · DBLP profile ↗
← Back
2ranked-venue papers
0as first author
2since 2021 · last 2024
0000-0002-0691-4554ORCID · reported

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 2 since 2021
YearPublicationVenuePosition
2024 Approximation Algorithms for the MAXSPACE Advertisement Problem
Lehilton L. C. Pedrosa, Mauro Roberto Costa da Silva, Rafael C. S. Schouery
Theory Comput. Syst.2
2023 Positional Knapsack Problem: NP-hardness and approximation scheme (Brief Announcement)
abstract
We present the Positional Knapsack Problem (PKP), show that it is NP-hard and admits a Fully Polynomial-Time Approximation Scheme (FPTAS). This problem is a variant of the classical Binary Knapsack Problem (KP) in which the contribution of an item to the objective function varies according to the position in which it is added. The change in the valuation adds new properties to the problem that do not hold for KP as PKP is not a generalization of KP. Our FPTAS is based on a dynamic programming algorithm and uses a recursive rounding approach, which is necessary since the objective function depends on each item's value and position.
Lehilton L. C. Pedrosa, Mauro Roberto Costa da Silva, Rafael C. S. Schouery
LAGOS2