I&C Journal 2002 Journal Article
Parallel Approximation Schemes for a Class of Planar and Near Planar Combinatorial Optimization Problems
- Harry B Hunt
- Madhav V Marathe
- Venkatesh Radhakrishnan
- S.S Ravi
- Daniel J Rosenkrantz
- Richard E Stearns
Define a (δ, g)-almost planar graph to be a graph G(V, E) consisting of vertex set V and a genus g layout with at most δ·|V| crossover nodes. We study a class of combinatorial optimization problems formulated as follows. Let X={x 1, x 2, …x n } be a set of variables each of which has a finite domain D={0, 1, …, poly(n)}. Also, let S be a fixed finite set of finite arity relations {R 1, …R q }. The optimization problem M AX -R ELATION (S) is the following: Given a set of terms {t 1, t 2, …, t m }, where each term t i is of the form f(x i 1, x i 2, …, x i r ) for some fϵS, assign values to each x i, 1≤i≤n, so as to maximize the number of satisfied terms. We show that for each fixed finite set S and fixed δ, g≥0, there is an NC-approximation scheme (NCAS) for the problem M AX -R ELATION (S) when restricted to instances whose bipartite graphs (that represent the variable-term relationship) are (δ, g)-almost planar. This result in conjunction with approximation-preserving reductions to M AX -R ELATION (S) enables us to obtain NCASs for a number of graph theoretic and satisfiability problems when restricted to (δ, g)-almost planar instances. Our results provide a characterization of a class of problems having an NCAS (and hence a PTAS).