Phd Proposal by Ezgi Karabulut

Event Details
  • Date/Time:
    • Friday September 16, 2016 - Saturday September 17, 2016
      11:00 am - 12:59 pm
  • Location: Groseclose 303 (Advisory Boardroom)
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:
No contact information submitted.

Summary Sentence: Auction Algorithms for Distributed Integer Programming Problems and Their Application to Online Setting

Full Summary: No summary paragraph submitted.

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)



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.


Additional Information

In Campus Calendar

Graduate Studies

Invited Audience
Phd proposal
  • Created By: Tatianna Richardson
  • Workflow Status: Draft
  • Created On: Sep 9, 2016 - 9:04am
  • Last Updated: Oct 7, 2016 - 10:19pm