On a Linear Program for Minimum-Weight Triangulation

• fiche de synthèse - matière potentielle : proof

On a Linear Program for Minimum-Weight Triangulation EXTENDED ABSTRACT∗ Arman Yousefi† Neal E. Young‡ Abstract Minimum-weight triangulation (MWT) is NP-hard. It has a polynomial-time constant-factor approxima- tion algorithm, and a variety of effective polynomial- time heuristics that, for many instances, can find the exact MWT. Linear programs (LPs) for MWT are well-studied, but previously no connection was known between any LP and any approximation algorithm or heuristic for MWT.

• sides of triangles in4
• mwt
• programming algorithm
• approximation algorithm
• linear programs
• edges
• 2 edges
• 1 lp
• lp
• triangles
• edge
• cost