Click here to skip to this page's main content.

New to the Open Library? — Learn how it works
Is Open Library useful to you? Chip in to keep it growing. Your gift will be matched today!   Donate
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 powered by WorldCat

Oh! The humanity! There's no description for this book yet. Can you help?
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

History Created December 11, 2009 · 2 revisions 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