### Abstract

We present a unified framework for designing polynomial time approximation schemes (PTASs) for "dense" instances of many script N sign script P sign-hard optimization problems, including maximum cut, graph bisection, graph separation, minimum k-way cut with and without specified terminals, and maximum 3-satisfiability. By dense graphs we mean graphs with minimum degree Ω(n), although our algorithms solve most of these problems so long as the average degree is Ω(n). Denseness for non-graph problems is defined similarly. The unified framework begins with the idea of exhaustive sampling: picking a small random set of vertices, guessing where they go on the optimum solution, and then using their placement to determine the placement of everything else. The approach then develops into a PTAS for approximating certain smooth integer programs, where the objective function and the constraints are "dense" polynomials of constant degree.

Original language | English (US) |
---|---|

Pages (from-to) | 193-210 |

Number of pages | 18 |

Journal | Journal of Computer and System Sciences |

Volume | 58 |

Issue number | 1 |

DOIs | |

State | Published - Feb 1999 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Networks and Communications
- Computational Theory and Mathematics
- Applied Mathematics

## Fingerprint Dive into the research topics of 'Polynomial time approximation schemes for dense instances of script N ℘-hard problems'. Together they form a unique fingerprint.

## Cite this

*Journal of Computer and System Sciences*,

*58*(1), 193-210. https://doi.org/10.1006/jcss.1998.1605