Abstract-Vi anser en klass av distribuerade submodulära maximeringsproblem där varje agent måste välja en enda strategi från sin strategi. Det globala målet är att maximera en submodulär funktion av de strategier som väljs av varje agent. Vid valet av strategi har varje agent tillgång till endast ett begränsat antal andra agenters val. För var och en av sina strategier kan en agent bedöma sitt marginella bidrag till det globala målet med tanke på dess information. Huvudsyftet är att undersöka hur denna begränsning av informationen om de strategier som andra agenter valt påverkar prestandan när agenter gör val enligt en lokal girig algoritm. I synnerhet ger vi lägre gränser på prestandan av giriga algoritmer för submodulär maximering, som beror på klicktalet av en graf som fångar informationsstrukturen. Vi karakteriserar också graf-teoretiska övre gränser i termer av det kromatiska antalet av grafen. Slutligen visar vi hur vissa grafegenskaper begränsar prestandan hos den giriga algoritmen. Simuleringar på flera vanliga modeller för slumpmässiga nätverk visar våra resultat.
Författarna till REF erbjuder övre och nedre gränser för SGA:s prestanda baserat på den underliggande DAG:s klicknummer.
Distributed Submodular Maximization With Limited Information
{'venue': 'IEEE Transactions on Control of Network Systems', 'journal': 'IEEE Transactions on Control of Network Systems', 'mag_field_of_study': ['Computer Science', 'Mathematics']}