Academic
Publications
Trading Off Solution Cost for Smaller Runtime in DCOP Search Algorithms (Extended Version)

Trading Off Solution Cost for Smaller Runtime in DCOP Search Algorithms (Extended Version),William Yeoh,Sven Koenig,Xiaoxun Sun

Trading Off Solution Cost for Smaller Runtime in DCOP Search Algorithms (Extended Version)  
BibTex | RIS | RefWorks Download
Distributed Constraint Optimization (DCOP) is a key tech- nique for solving multiagent coordination problems. Unfortunately, find- ing minimal-cost DCOP solutions is NP-hard. We therefore propose two mechanisms that trade off the solution costs of two DCOP search algo- rithms (ADOPT and BnB-ADOPT) for smaller runtimes, namely the Inadmissible Heuristics Mechanism and the Relative Error Mechanism. The solution costs that result from these mechanisms are bounded by a more meaningful quantity than the solution costs that result from the existing Absolute Error Mechanism since they both result in solution costs that are larger than minimal by at most a user-specified percent- age. Furthermore, the Inadmissible Heuristics Mechanism experimentally dominates both the Absolute Error Mechanism and the Relative Error Mechanism for BnB-ADOPT and is generally no worse than them for ADOPT.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.