Rounding in e-approximation algorithms

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

165 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 languageEnglish
Title of host publicationProceedings: IEEE SCVT 2006
Editors s.n
Place of PublicationLiege
PublisherIEEE
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

Fingerprint

Dive into the research topics of 'Rounding in e-approximation algorithms'. Together they form a unique fingerprint.

Cite this