Open Library logo
New Feature: You can now embed Open Library books on your website!   Learn More
Last edited by WorkBot
January 24, 2010 | History

Experiments concerning frugal path mechanisms 1 edition

Experiments concerning frugal path mechanisms
Tobi Kral

No ebook available.

Prefer the physical book? Check nearby libraries with:

Buy this book

There's no description for this book yet. Can you add one?
There is only 1 edition record, so we'll show it here...  •  Add edition?

Experiments concerning frugal path mechanisms.

Published 2005 .
Written in English.

About the Book

In the path selection problem, we must find the least expensive path between two given points in a graph. This problem is easily solved in classical graph theory but the associated mechanism design problem, in which we strive to design a mechanism that selects a path and induces truthful reporting of costs without paying a high premium, is not as elegantly solved. In fact, all path selection mechanisms can be forced to pay a prohibitively high premium for truthfulness. As the worst-case performance bound is the same for any mechanism, how a given mechanism behaves in practice becomes very important. In this thesis we investigate the performance of three proposed mechanisms in two real-life scenarios, one geographical and one network-based.

Edition Notes

Source: Masters Abstracts International, Volume: 44-02, page: 0935.

Advisor: A. Borodin.

Thesis (M.Sc.)--University of Toronto, 2005.

Electronic version licensed for access by U. of T. users.

GERSTEIN MICROTEXT copy on microfiche (2 microfiches).

The Physical Object

109 leaves.
Number of pages

ID Numbers

Open Library


Download catalog record: RDF / JSON
January 24, 2010 Edited by WorkBot add more information to works
December 11, 2009 Created by WorkBot add works page