Fast approximation algorithms for routing problems with hop-wise constraints

Amir Elalouf ()

Annals of Operations Research, 2014, vol. 222, issue 1, 279-291

Abstract: Given a graph G(N,A) with a cost (or benefit) and a delay on each arc, the constrained routing problem (CRP) aims to find a minimum-cost or a maximum-benefit path from a given source to a given destination node, subject to an end-to-end delay constraint. The problem (with a single constraint) is NP-hard, and has been studied by many researchers who found fully polynomial approximation schemes (FPAS) for this problem. The current paper focuses on a generalized CRP version, CRP with hop-wise constraints (CRPH). In the generalized version, instead of one constraint there are up to n−1 special-type constraints, where n is the number of nodes. An FPAS based on interval partitioning is proposed for both the minimization and the maximization versions of CRPH. For G(N,A) with n nodes and m arcs, the complexity of the algorithm is O(mn 2 /ε). Copyright Springer Science+Business Media New York 2014

Keywords: Approximation algorithms; Combinatorial problems; Shortest path; Routing (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-013-1308-5 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:222:y:2014:i:1:p:279-291:10.1007/s10479-013-1308-5

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-013-1308-5

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().