Rounding, Interval Partitioning and Separation

Authored by: Sartaj Sahni

Handbook of Approximation Algorithms and Metaheuristics, Second Edition

Print publication date:  May  2018
Online publication date:  May  2018

Print ISBN: 9781498770118
eBook ISBN: 9781351236423
Adobe ISBN:

10.1201/9781351236423-9

 Download Chapter

 

Abstract

This chapter reviews the three general methods—rounding, interval partitioning, and separation—proposed by Sahni [1] to transform pseudopolynomial-time algorithms into fully polynomial-time approximation schemes. The three methods, which generally apply to dynamic-programming and enumeration-type pseudopolynomial time algorithms, are illustrated using the 0/1-knapsack and multiconstrained shortest paths problems. Both of these problems are known to be NP-hard and both are solvable in pseudopolynomial time using either dynamic programming or enumeration.

 Cite
Search for more...
Back to top

Use of cookies on this website

We are using cookies to provide statistics that help us give you the best experience of our site. You can find out more in our Privacy Policy. By continuing to use the site you are agreeing to our use of cookies.