Abstract | ||
---|---|---|
Submodular maximization is an important problem with many applications in engineering, computer science, economics and social sciences. Since the problem is NP-Hard, a greedy algorithm has been developed, which gives an approximation within 1/2 of the optimal solution. This algorithm can be distributed among agents, each making local decisions and sharing that decision with other agents. Recent work has explored how the performance of the distributed algorithm is affected by a degradation in this information sharing. This work introduces the idea of strategy in these networks of agents and shows the value of such an approach in terms of the performance guarantees that it provides. In addition, an optimal strategy that gives such guarantees is identified. |
Year | DOI | Venue |
---|---|---|
2018 | 10.1109/CDC.2018.8619166 | 2018 IEEE CONFERENCE ON DECISION AND CONTROL (CDC) |
Field | DocType | ISSN |
Mathematical optimization,Computer science,Submodular maximization,Greedy algorithm,Distributed algorithm,Information sharing | Conference | 0743-1546 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
David Grimsman | 1 | 7 | 1.89 |
João P. Hespanha | 2 | 7674 | 587.34 |
Jason R. Marden | 3 | 676 | 56.57 |