DOS Seminar - Ezgi Karabulut

Event Details
  • Date/Time:
    • Monday April 17, 2017
      11:00 am - 12:00 pm
  • Location: Groseclose 402
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    N/A
  • Extras:
Contact
No contact information submitted.
Summaries

Summary Sentence: DOS Seminar - Ezgi Karabulut

Full Summary: No summary paragraph submitted.

TITLE:  Decentralized Online Integer Programming

ABSTRACT: 

We consider a set of collaborative agents that need to coordinate their actions so as to socially optimize the sum of their objectives while satisfying a common resource constraint. The objective functions of the players are unknown to them a priori and are revealed in an online manner over time. Given a resource allocation, each player’s action is determined by solving an integer program. Due to privacy issues, players want to share limited information while solving this problem in a decentralized way. A cardinality resource constraint links all player actions. The resulting problem is an online optimization problem to optimally allocate the resource among the players prior to observing the item values. The performance of an online algorithm is measured by regret, defined as the difference between the total gain of the best-fixed decision considering all data in hindsight and the total gain incurred by the online decisions we make. A good online algorithm is expected to have regret as a sublinear function of the number of rounds, T. In this research, we show that for any deterministic online algorithm for the resource allocation problem, there exist objective function coefficients that guarantee O(T) regret. Furthermore, for the case when the players' integer programs satisfy a special concavity condition, we propose a randomized online algorithm for the resource allocation problem that guarantees an upper bound of O(\sqrt T) on the expected regret.

 

Additional Information

In Campus Calendar
No
Groups

H. Milton Stewart School of Industrial and Systems Engineering (ISYE)

Invited Audience
Faculty/Staff, Public, Undergraduate students
Categories
No categories were selected.
Keywords
No keywords were submitted.
Status
  • Created By: phand3
  • Workflow Status: Published
  • Created On: Apr 14, 2017 - 5:01pm
  • Last Updated: Apr 14, 2017 - 5:01pm