Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials.
Viresh PatelGuus RegtsPublished in: SIAM J. Comput. (2017)
Keyphrases
- approximation algorithms
- undirected graph
- randomized algorithms
- special case
- constant factor
- approximation ratio
- np hard
- approximation guarantees
- disjoint paths
- worst case
- minimum cost
- vertex set
- set cover
- np hardness
- primal dual
- facility location problem
- vertex cover
- approximation schemes
- network design problem
- precedence constraints
- spanning tree
- random walk
- min cut
- directed acyclic graph
- bounded treewidth
- min cost
- bipartite graph
- directed graph
- computational complexity
- polynomial time approximation
- max flow
- search algorithm