Distributed constraint optimization: Difference between revisions

Revision as of 14:13, 27 April 2007

Revision as of 14:35, 27 April 2007

Line 37:

==Algorithms==

{| class="wikitable"

|-

! Algorithm Name

! Year Introduced

! Computational Complexity

! Memory Space Complexity

! [[Correctness]]

! [[Completeness]]

|-

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

{{Citation

| last1 = Modi | first1 = Pragnesh Jay

| last2 = Shen | first2 = Wei-Min

| last3 = Tambe | first3 = Milind

| last4 = Yokoo | first4 = Makoto

| contribution = An asynchronous complete method for distributed constraint optimization

| title = Proceedings of the second international joint conference on autonomous agents and multiagent systems

| publisher = [[Association_for_Computing_Machinery|ACM]] Press

| year = 2003

| pages = 161&ndash;168

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

| 2003

|

| Polynomial

| Proven

| Proven

|-

| '''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

|}

==Notes==