search

open-connectome-classes / StatConn-Spring-2015-Info

introductory material
18 stars 4 forks source link

Duality gap for graph matching? #244

Open mrjiaruiwang opened 9 years ago

mrjiaruiwang commented 9 years ago

Is there any way for us to formally prove a bound for the duality gap for the graph matching or "alignment" problem? It would be very interesting to know this bound because then we would be able to say something about the unrelaxed solution to the integer programming problem, which would take us closer to being able to solve IP's in deterministic polynomial time.

imichaelnorris commented 9 years ago

What is the duality gap for graph matching?

sgomezr commented 9 years ago

Is it similar to the 'duality gap' for fractional coloring of graphs?

mblohr commented 9 years ago

This paper discusses the alignment problem and the duality gap: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2648773/