Timezone: »

 
Spotlight
The Algebraic Path Problem for Graph Metrics
Enrique Fita Sanmartín · Sebastian Damrich · Fred Hamprecht

Tue Jul 19 11:50 AM -- 11:55 AM (PDT) @ Room 310
in Theory: Bandits/RL/Everything Else »

Finding paths with optimal properties is a foundational problem in computer science. The notions of shortest paths (minimal sum of edge costs), minimax paths (minimal maximum edge weight), reliability of a path and many others all arise as special cases of the "algebraic path problem" (APP). Indeed, the APP formalizes the relation between different semirings such as min-plus, min-max and the distances they induce. We here clarify, for the first time, the relation between the potential distance and the log-semiring. We also define a new unifying family of algebraic structures that include all above-mentioned path problems as well as the commute cost and others as special or limiting cases. The family comprises not only semirings but also strong bimonoids (that is, semirings without distributivity). We call this new and very general distance the "log-norm distance". Finally, we derive some sufficient conditions which ensure that the APP associated with a semiring defines a metric over an arbitrary graph.

Keywords: T: Everything Else · MISC: Everything Else

Author Information

Enrique Fita Sanmartín (Heidelberg University)
Sebastian Damrich (Heidelberg University)
Fred Hamprecht (Heidelberg Collaboratory for Image Processing)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors