An FPTAS for budgeted laminar matroid independent set
OPERATIONS RESEARCH LETTERS(2023)
摘要
We study the budgeted laminar matroid independent set problem. The input is a ground set, where each element has a cost and a non-negative profit, along with a laminar matroid over the elements and a budget. The goal is to select a maximum profit independent set of the matroid whose total cost is bounded by the budget. We present a fully polynomial-time approximation scheme (FPTAS) for the problem, improving the previous efficient PTAS for this matroid family. (c) 2023 Elsevier B.V. All rights reserved.
更多查看译文
关键词
FPTAS,Laminar matroids,Knapsack,Dynamic programming
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要