Improved Approximation Algorithms for Weighted Hypergraph Embedding in a Cycle

DOI10.1137/050631951zbMATH Open1151.05326OpenAlexW2019149868MaRDI QIDQ3544271FDOQ3544271

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

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

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)

Cited In (8)

• 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
• 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)