BEGIN:VCALENDAR
PRODID:-//Microsoft Corporation//Outlook MIMEDIR//EN
VERSION:1.0
BEGIN:VEVENT
DTSTART:20121114T233000Z
DTEND:20121115T000000Z
LOCATION:355-EF
DESCRIPTION;ENCODING=QUOTED-PRINTABLE:ABSTRACT: Network alignment is an optimization problem to find the best one-to-one=0Amap between the vertices of a pair of graphs that overlaps in as many edges =0Aas possible.=0AIt is a relaxation of the graph isomorphism=0Aproblem and is closely related to the subgraph isomorphism problem.=0AThe best current approaches are entirely heuristic and iterative in nature.=0AThey generate real-valued heuristic weights that must be rounded to=0Afind integer solutions. This rounding requires solving a bipartite maximum weight=0Amatching problem at each iteration in order to avoid missing=0Ahigh quality solutions. =0AWe investigate substituting a parallel, half-approximation for maximum=0Aweight matching instead of an exact computation. Our experiments show=0Athat the resulting difference in solution quality is negligible.=0AWe demonstrate almost a 20-fold speedup using 40 threads on an 8 processor=0A Intel Xeon E7-8870 system and now solve real-world problems in 36 seconds instead of =0A10 minutes.
SUMMARY:A Multithreaded Algorithm for Network Alignment via Approximate Matching
PRIORITY:3
END:VEVENT
END:VCALENDAR
BEGIN:VCALENDAR
PRODID:-//Microsoft Corporation//Outlook MIMEDIR//EN
VERSION:1.0
BEGIN:VEVENT
DTSTART:20121114T233000Z
DTEND:20121115T000000Z
LOCATION:355-EF
DESCRIPTION;ENCODING=QUOTED-PRINTABLE:ABSTRACT: Network alignment is an optimization problem to find the best one-to-one=0Amap between the vertices of a pair of graphs that overlaps in as many edges =0Aas possible.=0AIt is a relaxation of the graph isomorphism=0Aproblem and is closely related to the subgraph isomorphism problem.=0AThe best current approaches are entirely heuristic and iterative in nature.=0AThey generate real-valued heuristic weights that must be rounded to=0Afind integer solutions. This rounding requires solving a bipartite maximum weight=0Amatching problem at each iteration in order to avoid missing=0Ahigh quality solutions. =0AWe investigate substituting a parallel, half-approximation for maximum=0Aweight matching instead of an exact computation. Our experiments show=0Athat the resulting difference in solution quality is negligible.=0AWe demonstrate almost a 20-fold speedup using 40 threads on an 8 processor=0A Intel Xeon E7-8870 system and now solve real-world problems in 36 seconds instead of =0A10 minutes.
SUMMARY:A Multithreaded Algorithm for Network Alignment via Approximate Matching
PRIORITY:3
END:VEVENT
END:VCALENDAR