A polynomial time approximation scheme for embedding a directed hypergraph on a weighted ring

A polynomial time approximation scheme for embedding a directed hypergraph on a weighted ring

0.00 Avg rating—0 Votes
Article ID: iaor20125707
Volume: 24
Issue: 3
Start Page Number: 319
End Page Number: 328
Publication Date: Oct 2012
Journal: Journal of Combinatorial Optimization
Authors: , ,
Keywords: approximation, hypergraphs, polynomial programs
Abstract:

Given a directed hypergraph H=(V,E H ), we consider the problem of embedding all directed hyperedges on a weighted ring. The objective is to minimize the maximum congestion which is equal to the maximum product of the weight of a link and the number of times that the link is passed by the embedding. In this paper, we design a polynomial time approximation scheme for this problem.

Reviews

Required fields are marked *. Your email address will not be published.