On a Linear Program for Minimum-Weight Triangulation

Details On a Linear Program for Minimum-Weight Triangulation On a Linear Program for Minimum-Weight Triangulation

2011-11-22

arxiv.org/abs/1111.5305v1

Computer Science

Computational Geometry

Extended abstract appeared in SODA 2012

Scientific paper

Minimum-weight triangulation (MWT) is NP-hard. It has a polynomial-time constant-factor approximation 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. Here we show the first such connections: for an LP formulation due to Dantzig et al. (1985): (i) the integrality gap is bounded by a constant; (ii) given any instance, if the aforementioned heuristics find the MWT, then so does the LP.

Affiliated with

Also associated with

No associations

Rating

On a Linear Program for Minimum-Weight Triangulation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On a Linear Program for Minimum-Weight Triangulation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On a Linear Program for Minimum-Weight Triangulation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-554351