An Approximation Algorithm for the Discrete Team Decision Problem

DOI10.1137/050628374MaRDI QIDQ5294589zbMATH OpenOpenAlexFDO

Authors Randy Cogill, Sanjay Lall

Publication date 25 July 2007

Published in SIAM Journal on Control and Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0605188, https://semanticscholar.org/paper/75fb30b248e3cc0a203d436ef894df5e20f6d970

zbMATH Keywords

approximation algorithmsdecentralized controlteam theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Decision theory (91B06) Decentralized systems (93A14) Control/observation systems with incomplete information (93C41)

Abstract: In this paper we study a dynamic resource allocation problem which we call the stochastic k-server problem. In this problem, requests for some service to be performed appear at various locations over time, and we have a collection of k mobile servers which are capable of servicing these requests. When servicing a request, we incur a cost equal to the distance traveled by the dispatched server. The goal is to find a strategy for choosing which server to dispatch to each incoming request which keeps the average service cost as small as possible. In the model considered in this paper, the locations of service requests are drawn according to an IID random process. We show that, given a statistical description of this process, we can compute a simple decentralized state-feedback policy which achieves an average cost within a factor of two of the cost achieved by an optimal state-feedback policy. In addition, we demonstrate similar results for several extensions of the basic stochastic k-server problem.

Recommendations

• On the complexity of decentralized decision making and detection problems
• Intractable Problems in Control Theory
• Smooth optimal decision strategies for static team optimization problems and their approximations
• A Class of Team Problems with Discrete Action Spaces: Optimality Conditions Based on Multimodularity
• Regularized stochastic team problems

Cited in

(7)

• Team selection factor pricing with discrete and inhomogeneous factors
• A simple greedy algorithm for the profit-aware social team formation problem
• Integer programming approaches to the multiple team formation problem
• Team theory and person-by-person optimization with binary decisions
• A Class of Team Problems with Discrete Action Spaces: Optimality Conditions Based on Multimodularity
• Correlation decay in random decision networks
• An algorithmic approach to identify irrelevant information in sequential teams

This page was built for publication: An Approximation Algorithm for the Discrete Team Decision Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5294589)