Multiconstrained QoS Routing: Greedy Is Good

A fundamental problem in Quality-of-Service (QoS) routing is to find a path connecting a source node to a destination node that satisfies K ¡Ý 2 additive QoS constraints. This MultiConstrained Path problem (MCP) is known to be NP-complete. In a recent paper, Xue et al. showed that the shortest path with respect to a single auxiliary edge weight obtained by combining the K edge weights into a single metric is a K-approximation to MCP, in the sense that the largest ratio of path weight over its corresponding constraint is within a factor of K from minimum. This paper presents a simple greedy algorithm and proves that this greedy algorithm is also a K-approximation algorithm to MCP.