The Library
FPT-approximation for FPT problems
Tools
Lokshtanov, Daniel, Misra, Pranabendu, Sridharan, Ramanujan, Saurabh, Saket and Zehavi, Meirav (2021) FPT-approximation for FPT problems. In: ACM-SIAM Symposium on Discrete Algorithms (SODA) 2021, Virtual, 10-13 Jan 2021. Published in: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) ISBN 9781611976465. doi:10.1137/1.9781611976465.14
|
PDF
WRAP-FPT-approximation-FPT-problems-Sridharan-2021.pdf - Accepted Version - Requires a PDF viewer. Download (700Kb) | Preview |
Official URL: https://doi.org/10.1137/1.9781611976465.14
Abstract
Over the past decade, many results have focused on the design of parameterized approximation algorithms for W[1]-hard problems. However, there are fundamental problems within the class FPT for which the best known algorithms have seen no progress over the course of the decade. In this paper, we expand the study of FPT-approximation and initiate a systematic study of FPT-approximation for problems that are in FPT. We design FPT-approximation algorithms for problems that are in FPT, with running times that are significantly faster than the corresponding best known FPT-algorithm, and while achieving approximation ratios that are significantly better than what is possible in polynomial time.
Item Type: | Conference Item (Paper) | ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||||||||||||
Library of Congress Subject Headings (LCSH): | Computer algorithms, Approximation theory -- Data processing, Computer communication systems | ||||||||||||||||||
Journal or Publication Title: | Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) | ||||||||||||||||||
Publisher: | Society for Industrial and Applied Mathematics | ||||||||||||||||||
ISBN: | 9781611976465 | ||||||||||||||||||
Official Date: | 2021 | ||||||||||||||||||
Dates: |
|
||||||||||||||||||
DOI: | 10.1137/1.9781611976465.14 | ||||||||||||||||||
Status: | Peer Reviewed | ||||||||||||||||||
Publication Status: | Published | ||||||||||||||||||
Reuse Statement (publisher, data, author rights): | “First Published in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) in 2021, published by the Society for Industrial and Applied Mathematics (SIAM)” “Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.”) | ||||||||||||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||||||||||||
Date of first compliant deposit: | 24 November 2020 | ||||||||||||||||||
Date of first compliant Open Access: | 1 February 2021 | ||||||||||||||||||
RIOXX Funder/Project Grant: |
|
||||||||||||||||||
Conference Paper Type: | Paper | ||||||||||||||||||
Title of Event: | ACM-SIAM Symposium on Discrete Algorithms (SODA) 2021 | ||||||||||||||||||
Type of Event: | Conference | ||||||||||||||||||
Location of Event: | Virtual | ||||||||||||||||||
Date(s) of Event: | 10-13 Jan 2021 | ||||||||||||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year