An almost four-approximation algorithm for maximum weight triangulation

DOI10.1007/S10878-008-9158-9MaRDI QIDQ2268761zbMATH OpenOpenAlexFDO

Authors Shiyan Hu

Publication date 9 March 2010

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-008-9158-9

zbMATH Keywords

approximation algorithmtriangulationapproximation ratiomaximum weight triangulationspoke triangulation

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Computing and Combinatorics
• New results for the minimum weight triangulation problem
• Quasi-Greedy Triangulations Approximating the Minimum Weight Triangulation
• A New Heuristic for Minimum Weight Triangulation
• On approximation behavior of the greedy triangulation for convex polygons

Cites work

• scientific article; zbMATH DE number 871937 (Why is no real title available?)
• scientific article; zbMATH DE number 1446325 (Why is no real title available?)
• A New Heuristic for Minimum Weight Triangulation
• A heuristic triangulation algorithm
• A linear-time approximation scheme for maximum weight triangulation of convex polygons
• A linear-time approximation scheme for minimum weight triangulation of convex polygons
• A quasi-polynomial time approximation scheme for minimum weight triangulation
• Computing and Combinatorics
• Maximum weight triangulation and graph drawing
• Minimum weight triangulation is NP-hard
• New results for the minimum weight triangulation problem
• Quasi-Greedy Triangulations Approximating the Minimum Weight Triangulation

Cited in

(3)

• A note on a QPTAS for maximum weight triangulation of planar point sets
• Finding a maximum weight triangle in n ^3-Δ time, with applications
• Computing and Combinatorics

This page was built for publication: An almost four-approximation algorithm for maximum weight triangulation

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