Vi anser att AC elektriska system där varje elektrisk enhet har ett strömbehov uttryckt som ett komplext antal, och det finns en gräns för omfattningen av den totala strömförsörjningen. Motiverade av detta scenario, introducerar vi den komplexa-efterfrågan knapsack problem (C-KP), en ny variation av den traditionella knapsack problem, där varje post är associerad med en efterfrågan som ett komplext tal, snarare än ett reellt tal som ofta tolkas som vikt eller storlek på objektet. Samtidigt hålla samma mål som att maximera summan av värden för de valda objekten, sätter vi kapacitetsgränsen på storleken på summan av nöjda krav. För C-KP bevisar vi dess oåtkomlighet genom FPTAS (om inte P = NP), samt presenterar en (1/2 − )-tillnärmningsalgoritm. Dessutom undersöker vi den själviska multiagentmiljö där varje agent är ansvarig för en vara, och en agent kan felrapportera efterfrågan och värdet av sin vara för sitt eget intresse. Vi visar ett enkelt sätt att anpassa vår approximationsalgoritm till monoton, vilket är tillräckligt för förekomsten av incitamentskompatibla betalningar så att ingen agent har ett incitament att felrapportera. Våra resultat ger en inblick i utformningen av multiagentsystem för smarta nät.
REF erhöll en approximation på 1 2 för det fall där 0 ≤. ≤..................................................................................................
Complex-Demand Knapsack Problems and Incentives in AC Power Systems
{'venue': None, 'journal': 'arXiv: Data Structures and Algorithms', 'mag_field_of_study': ['Mathematics', 'Computer Science']}