ALGORITHMIC CHALLENGES IN LEARNING PATH METRICS FROM OBSERVED CHOICES
In many systems it is an essential part of the operation to find optimal paths in large graphs. In order to understand the system, we need to know the path metric under which the optimal paths are chosen. In many cases, however, no explicite knowledge of the metric is available, we can only observe the path choices that are made. Our goal is to learn the unknown metric, as accurately as possible, from the observed path choices. We present a mathematical model and method to handle this problem. Our main result is that the unknonw path metric can be optimally learned by a polynomial time algorithm, if we assume an additive (but unknown) metric over the graph edges. We also consider the case when the path metric is general, that is, not necessarily additive.
Document Type: Research Article
Affiliations: Department of Computer Science, The University of Texas at Dallas, Richardson, Texas, USA
Publication date: 01 August 2008
- Information for Authors
- Subscribe to this Title
- Ingenta Connect is not responsible for the content or availability of external websites
- Access Key
- Free content
- Partial Free content
- New content
- Open access content
- Partial Open access content
- Subscribed content
- Partial Subscribed content
- Free trial content