Decentralized online integer programming problems with a coupling cardinality constraint

Karabulut Türkseven, Ezgi and Ahmed, Shabbir and Nemhauser, George (2021) Decentralized online integer programming problems with a coupling cardinality constraint. Computers and Operations Research, 135 . ISSN 0305-0548 (Print) 1873-765X (Online)

Full text not available from this repository. (Request a copy)

Abstract

We consider a problem involving a set of agents who need to coordinate their actions to optimize the sum of their objectives while satisfying a common resource constraint. The objective functions of the agents are unknown to them a priori and are revealed in an online manner. The resulting problem is an online optimization problem to optimally allocate the resource among the agents prior to observing the objective functions. For any deterministic online algorithm for this problem, it has been shown that there exists a lower bound of Ω(T) on regret. When the agents’ integer programs satisfy a discrete concavity condition, we propose a randomized online algorithm that is decentralized and guarantees an upper bound of O(KTlnm) on the expected regret, where K is the total amount of resource to be shared and m is the number of agents.
Item Type: Article
Uncontrolled Keywords: Decentralized optimization; Distributed integer programming; Online optimization; Resource allocation
Divisions: Faculty of Engineering and Natural Sciences
Depositing User: Ezgi Karabulut Türkseven
Date Deposited: 01 Sep 2022 20:46
Last Modified: 01 Sep 2022 20:46
URI: https://research.sabanciuniv.edu/id/eprint/43525

Actions (login required)

View Item
View Item