On solving a non-convex quadratic programming problem involving resistance distances in graphs

Quadratic programming problems involving distance matrix ( D ) that arises in trees are considered in the literature by Dankelmann (Discrete Math 312:12–20, 2012 ), Bapat and Neogy (Ann Oper Res 243:365–373, 2016 ). In this paper, we consider the question of solving the quadratic programming problem...

Full description

Saved in:
Bibliographic Details
Published in:Annals of operations research 2020-04, Vol.287 (2), p.643-651
Main Authors: Dubey, Dipti, Neogy, S. K.
Format: Article
Language:English
Subjects:
Analysis
Business and Management
Combinatorics
Distance matrices
Graphic methods
Graphs
Mathematical programming
Matrices (mathematics)
Methods
Operations research
Operations Research/Decision Theory
Problem solving
Quadratic programming
S.I.: Game theory and optimization
Studies
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Quadratic programming problems involving distance matrix ( D ) that arises in trees are considered in the literature by Dankelmann (Discrete Math 312:12–20, 2012 ), Bapat and Neogy (Ann Oper Res 243:365–373, 2016 ). In this paper, we consider the question of solving the quadratic programming problem of finding maximum of x T R x subject to x being a nonnegative vector with sum 1 and show that for the class of simple graphs with resistance distance matrix ( R ) which are not necessarily a tree, this problem can be reformulated as a strictly convex quadratic programming problem. An application to symmetric bimatrix game is also presented.
ISSN:0254-5330
1572-9338
DOI:10.1007/s10479-018-3018-5