Graphs Approach Hypermetric Inequalities via
Topological Spaces

R. Apparsamy; Dr. N. Selvi

doi:https://doi.org/10.14445/22315373/IJMTT-V52P563

International Journal of Mathematics Trends and Technology

Research Article | Open Access | Download PDF

Volume 52 | Number 7 | Year 2017 | Article Id. IJMTT-V52P563 | DOI : https://doi.org/10.14445/22315373/IJMTT-V52P563

Graphs Approach Hypermetric Inequalities via Topological Spaces

R. Apparsamy, Dr. N. Selvi

Citation :

R. Apparsamy, Dr. N. Selvi, "Graphs Approach Hypermetric Inequalities via Topological Spaces," International Journal of Mathematics Trends and Technology (IJMTT), vol. 52, no. 7, pp. 445-448, 2017. Crossref, https://doi.org/10.14445/22315373/IJMTT-V52P563

Abstract

Hypermetric Topology inequalities have many applications in the planar graphs and most recently in the approximate solution to the graphs by linear and semi definite programming. However, not much is known about the separation problem for these inequalities. In this paper we show that similar results holds for inequalities of negative type, even though the separation problem for negative type inequalities is well known to be solvable in polynomial time. We also show similar results hold for the more general k-konal and gap inequalities.

Keywords

Hypermetric, k-konal, gapinequality, negative type inequality, pure, cayley.

References

1. Avis, D., and Grishukhin, V.P.: A Bound on the k-gonality of Facets of the Hyper- metric Cone and Related Complexity Problems, Computational Geometry: Theory and Applications 2 (1993) 241-254.
2. Avis, D., and Umemoto, J.: Stronger Linear Programming Relaxations of Max-Cut, Les cahiers du GERAD G-2002-48, September, 2002.
3. Deza, M. (Tylkin, M.E.): Realizablility of Distance Matrices in Unit Cubes (in Russian), Problem Kybernetiki 7 (1962) 31-42.
4. Deza, M., Grishukhin, V.P., and Laurent, M.: The Hypermetric Cone is Polyhedral, Combinatorical 13 (1993) 397-411.
5. Deza, M., and Laurent, M.: Geometry of Cuts and Metrics, Springer, 1997.
6. Garey M.R., Johnson D.S., Computers and Intractability, W.H.Freeman and Co 1979.
7. Helmberg, C., and Rendl, F.: Solving Quadratic (0,1)-Problems by Semi definite Programs and Cutting Planes, Math. Prog . 82 (1998) 291-315.
8. Laurent, M., and Poljak, S.: Gap Inequalities for the Gap Polytope, Europ. J. Combinatrics 17 (1996) 233-254.
9. Reed, B.: A Gentle Introduction to Semi-Definite Programming, in Perfect Graphs, ed. J. Alfons´ and B. Reed, Wiley, (2001).