*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Thesis Title: Auction Algorithms for Distributed Integer Programming Problems and Their Application to Online Setting
Advisors: Dr. George Nemhauser and Dr. Shabbir Ahmed
Committee members: Dr. Natashia Boland, Dr. Santanu Dey
Date and Time: Friday, September 16 2016, 11:00 AM.
Location: Groseclose 303 (Advisory Boardroom)
Abstract:
Distributed optimization is an active research area with the involvement of multiple processors to solve optimization problems. The motivation for distributed optimization may either be big data that is difficult to store or process on a single machine, or independent agents that do not want to fully cooperate and share their data. Currently, most of the discrete optimization algorithms that are parallelizable require a central processor to coordinate the solutions. We propose algorithms to break this master-slave relationship between the processors and assign equal roles to every processor. The auction algorithm that we present addresses solving integer programming problems coupled with a knapsack constraint. We prove optimality of our auction algorithm for problems with a concavity property, and give examples of problems that have this concavity property. Furthermore, we give error bounds of the auction algorithm when applied to problems that don’t have the concavity property but have a concave approximation function and we give example concave approximations. As future work, we propose to carry the auction algorithm to an online setting. We will design auction protocols to ensure sublinear regret bounds.
