Distributed constraint optimization: Difference between revisions

Revision as of 14:35, 27 April 2007

Revision as of 14:58, 27 April 2007

Line 41:

! Algorithm Name

! Year Introduced

! [[Computational complexity theory|Complexity]]

! [[Correctness]]/<br />[[Completeness]]

! Memory Space Complexity

! Implementations

! [[Correctness]]

|-

! [[Completeness]]

| '''DPOP'''<br />Distributed Pseudotree Optimization Procedure<ref name="petcu04distributed">

{{Citation

| last1 = Petcu | first1 = Adrian

| last2 = Faltings | first2 = Boi

| contribution = A Distributed, Complete Method for Multi-Agent Constraint Optimization

| title = Proceedings of the Fifth International Workshop on Distributed Constraint Reasoning

| date = September

| year = 2004

| contribution-url = http://liawww.epfl.ch/Publications/Archive/Petcu2004b.pdf}}</ref>

| 2004

| ''Memory:'' Exponential

| Proven

| ''Reference Implementation:'' [http://liawww.epfl.ch/frodo/ FRODO] (free but proprietary)<br />

[http://dcopolis.sourceforge.net/ DCOPolis] ([[GNU GPL]])

| -

| '''OptAPO'''<br />Asynchronous Partial Overlay<ref name="mailler04solving">

{{Citation

| last1 = Mailler | first1 = Rober

| last2 = Lesser | first2 = Victor

| contribution = Solving Distributed Constraint Optimization Problems Using Cooperative Mediation

| title = Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems

| pages = 438&ndash;445

| publisher = [[IEEE_Computer_Society]]

| year = 2004

| contribution-url = ftp://mas.cs.umass.edu/pub/mailler/mailler-569.pdf}}</ref>

| 2004

|

| Proven

| ''Reference Implementation:'' [http://www.ai.sri.com/~mailler/optapo.html OptAPO]<br />

[http://dcopolis.sf.net/ DCOPolis] ([[GNU GPL]]; In Development)

|-

| '''Adopt'''<br />Asynchronous Backtracking<ref name="modi03asynchronous">

Line 59 ⟶ 89:

| contribution-url = http://teamcore.usc.edu/papers/2004/aij-modi.pdf}}</ref>

| 2003

| ''Memory:'' Polynomial

|

| Polynomial

| Proven

| Proven

| ''Reference Implementation:'' [http://teamcore.usc.edu/dcop/ Adopt]<br />

[http://dcopolis.sf.net/ DCOPolis] ([[GNU GPL]])

|-

| '''DPOP'''<br />Distributed Pseudotree Optimization Procedure<ref name="petcu04distributed">

{{Citation

| last1 = Petcu | first1 = Adrian

| last2 = Faltings | first2 = Boi

| contribution = A Distributed, Complete Method for Multi-Agent Constraint Optimization

| title = Proceedings of the Fifth International Workshop on Distributed Constraint Reasoning

| publisher = [[Association_for_Computing_Machinery|ACM]] Press

| date = September

| year = 2004

| contribution-url = http://liawww.epfl.ch/Publications/Archive/Petcu2004b.pdf}}</ref>

| 2004

|

| Exponential

| Proven

| Proven

|}