Improved Approximation Algorithms for Weighted Hypergraph Embedding in a Cycle

DOI10.1137/050631951MaRDI QIDQ3544271zbMATH OpenOpenAlexFDO

Authors Hann-Jang Ho, Sing-Ling Lee

Publication date 5 December 2008

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/050631951

zbMATH Keywords

approximation algorithmhypergraphlinear programmingNP-completeweighted hypergraph embedding in a cycle

Mathematics Subject Classification ID

Hypergraphs (05C65) Approximation algorithms (68W25) Linear programming (90C05) Combinatorial optimization (90C27)

Recommendations

• On minimizing the maximum congestion for weighted hypergraph embedding in a cycle
• A 2-approximation algorithm for an embedded hypergraph in a weighted cycle
• A polynomial time approximation scheme for embedding hypergraph in a weighted cycle
• A polynomial time approximation scheme for embedding hypergraph in a weighted cycle
• A polynomial-time approximation scheme for embedding hypergraph in a cycle

Cited in

(9)

• On minimizing the maximum congestion for weighted hypergraph embedding in a cycle
• A polynomial time approximation scheme for embedding a directed hypergraph on a weighted ring
• Improved approximation algorithms for embedding hyperedges in a cycle
• A polynomial time approximation scheme for embedding hypergraph in a weighted cycle
• Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs
• A 2-approximation algorithm for an embedded hypergraph in a weighted cycle
• Automata, Languages and Programming
• A polynomial time approximation scheme for embedding hypergraph in a weighted cycle
• Weighted nearest neighbor algorithms for the graph exploration problem on cycles

This page was built for publication: Improved Approximation Algorithms for Weighted Hypergraph Embedding in a Cycle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3544271)