Conditionally Optimal Approximation Algorithms for the Girth of a Directed Graph.
Mina DalirrooyfardVirginia Vassilevska WilliamsPublished in: ICALP (2020)
Keyphrases
- approximation algorithms
- directed graph
- disjoint paths
- worst case
- undirected graph
- minimum cost
- constant factor
- np hard
- random walk
- special case
- vertex cover
- approximation schemes
- approximation guarantees
- set cover
- primal dual
- approximation ratio
- strongly connected
- strongly np hard
- optimal solution
- directed acyclic graph
- graph structure
- open shop
- winner determination
- greedy algorithm
- directed edges
- upper bound
- error bounds
- maximum flow
- combinatorial auctions
- np hardness
- randomized algorithms
- network flow
- scheduling problem
- dynamic programming
- precedence constraints