Abstract-The uppdragsproblem utgör ett av de grundläggande problemen i samband med linjär programmering. Förutom dess teoretiska betydelse, dess frekventa utseende inom områdena distribuerad kontroll och anläggning allokering, där problemens storlek och kostnaden för global beräkning och information kan vara mycket oöverkomlig, ger upphov till behovet av lokala lösningar som dynamiskt tilldelar distinkta agenter till distinkta uppgifter, samtidigt som den totala tilldelningsnyttan maximeras. I detta dokument tar vi hänsyn till problemet med linjär tilldelning i samband med nätverksanslutna system, där den största utmaningen är att hantera bristen på global information på grund av agenternas begränsade kommunikationskapacitet. Vi tar itu med denna utmaning med hjälp av en distribuerad auktionsalgoritm, där agenterna kan bjuda på den uppgift som de vill tilldelas. Det önskade uppdraget bygger på ett lämpligt urval av anbud som bestämmer priset på uppgifterna och gör dem mer eller mindre attraktiva för agenterna att lägga bud på. Senast tillgänglig prisinformation, nödvändig för korrekt budgivning, kan erhållas på ett multi-hop-sätt genom lokal kommunikation mellan angränsande agenter. Vår algoritm är en förlängning till den parallella auktionsalgoritm som föreslagits av Bertsekas et al till det fall där endast lokal information finns tillgänglig och det visas att den alltid konvergerar till ett uppdrag som maximerar den totala tilldelningsnyttan inom en linjär approximation av den optimala.
Mer nyligen, ett särskilt fall av tilldelningsproblem, som behandlar bristen på global information och begränsad kommunikationskapacitet, löses av en distribuerad auktionsalgoritm som maximerar den totala tilldelningen inom en linjär approximation av den optimala lösningen REF.
A distributed auction algorithm for the assignment problem
{'venue': '2008 47th IEEE Conference on Decision and Control', 'journal': '2008 47th IEEE Conference on Decision and Control', 'mag_field_of_study': ['Computer Science']}