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

linear programmingapproximation algorithmhypergraphNP-completeweighted hypergraph embedding in a cycle

Mathematics Subject Classification ID

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

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)

• Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs
• Weighted nearest neighbor algorithms for the graph exploration problem on cycles
• Automata, Languages and Programming
• Improved approximation algorithms for embedding hyperedges in a cycle
• 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 a directed hypergraph on a weighted ring

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)