A Note on ``A linear-size zero-one programming model for the minimum spanning tree problem in planar graphs"
Hamidreza Validi (hamidreza.validiokstate.edu)
Abstract: In the paper ``A linear-size zero-one programming model for the minimum spanning tree problem in planar graphs'' (Networks 39(1):53--60, 2002), Williams introduced an extended formulation for the spanning tree polytope of a planar graph. This formulation is remarkably small (using only $O(n)$ variables and constraints) and remarkably strong (defining an integral polytope). In this note, we point out that Williams' formulation, as originally stated, is incorrect. Specifically, we construct a binary feasible solution to Williams' formulation that does not represent a spanning tree. Fortunately, there is a simple fix, which is to restrict the choice of the root vertices in the primal and dual spanning trees, whereas Williams explicitly allowed them to be chosen arbitrarily. The same flaw and fix apply to a subsequent formulation of Williams (``A Zero-One Programming Model for Contiguous Land Acquisition.'' Geographical Analysis 34(4): 330-349, 2002).
Keywords: spanning tree; planar graph; planar dual; extended formulation; extension complexity; spanning arborescence; integer programming;
Category 1: Integer Programming
Category 2: Combinatorial Optimization
Citation: Published in Networks: https://onlinelibrary.wiley.com/doi/full/10.1002/net.21849 Freely available at: https://docs.google.com/viewer?a=v&pid=sites&srcid=ZGVmYXVsdGRvbWFpbnxhdXN0aW5sYnVjaGFuYW58Z3g6M2U4YzBiZTY2NDVjMGYyYg
Entry Submitted: 07/04/2018
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|