A parameterized approximation algorithm is a method for finding approximate solutions to NP-hard optimization problems in time that is polynomial in the input size and some function of a chosen parameter, combining ideas from two separate traditions in algorithm design. Ordinary approximation algorithms guarantee a solution within a fixed factor of optimal in polynomial time, while fixed-parameter tractable algorithms find exact solutions in time that is polynomial in the input size plus a function of a parameter k; a parameterized approximation algorithm computes an alpha-approximate solution in f(k) times a polynomial in n, giving a stronger quality guarantee than a standard approximation while keeping the efficiency profile of a fixed-parameter tractable algorithm. Researchers including Marx, and later Feldmann and colleagues, have surveyed the area as a framework for computationally hard optimization problems.
Facts
Classification
Design TechniqueHeuristic or Approximation 1 Connections
In Field
Source Parameterized approximation algorithm (Wikipedia)
Uses Design Technique
Entity-backed identity for the design-technique enum value this algorithm already carries, resolved to a computing concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The design-technique fact itself stays on the algorithm unchanged.
Entity-backed identity for the design-technique enum value this algorithm already carries, resolved to a computing concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The design-technique fact itself stays on the algorithm unchanged.
Sources
1. Parameterized approximation algorithm (Wikipedia)
Wikipedia lead/infobox
A parameterized approximation algorithm is a type of algorithm that aims to find approximate solutions to NP-hard optimization pr
In Field: Algorithms and Complexity Theory, Lead sentence
parameterized approximation algorithm is a type of algorithm that aims to find approximate solutions to NP-hard optimization problems in polynomial time in the input size and a function of a specific parameter.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.