Rounding in e-approximation algorithms

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

14 Downloads (Pure)

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.
Original languageUndefined/Unknown
Title of host publicationProceedings: IEEE SCVT 2006
Editors s.n
Place of PublicationLiege
PublisherIEEE Society
Pages1-4
Number of pages4
ISBN (Print)0780397851
DOIs
Publication statusPublished - 2006
EventIEEE SCVT 2006 - Liege, Belgium
Duration: 23 Nov 2006 → …

Publication series

Name
PublisherIEEE

Conference

ConferenceIEEE SCVT 2006
Period23/11/06 → …

Keywords

  • conference contrib. refereed
  • Conf.proc. > 3 pag

Cite this

Kuipers, FA. (2006). Rounding in e-approximation algorithms. In s.n (Ed.), Proceedings: IEEE SCVT 2006 (pp. 1-4). IEEE Society. https://doi.org/10.1109/SCVT.2006.334379