Rounding in e-approximation algorithms

Conference paper (2006)

Authors

F.A. Kuipers Network Architectures and Services - EEMCS
Research Group
Network Architectures and Services (EEMCS) (TU Delft)
Copyright: © 2006 F.A. Kuipers
DOI: https://doi.org/10.1109/SCVT.2006.334379
More Info
expand_more

Published Date

2006

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Quantum & Computer Engineering

Research Group

Network Architectures and Services

Abstract

A common approach to deal with NP-hard problems is to deploy polymonial-time e-approximation algorithms often resort to rounding and scaling to guarantee a solution that is within a factor ( 1+ypsilon) of the optimal solution. Usually, researchers either only round up or only down. In this paper we will evaluate the gian in accuracy when rounding up and down. The main application of this technique upon which we focus is Quality Service routing and specifically the Restricted Shortest Path Problem.

Files

SCVT2006.pdf
(.pdf | 0.347 Mb)