@InProceedings{liu95a,
  author =	 {JyiShane Liu and Katia P. Sycara},
  title =	 {Exploiting Problem Structure for Distributed
                  Constraint Optimization},
  googleid =	 {upDd-8nh8fAJ:scholar.google.com/},
  booktitle =	 {Proceedings of the First International Conference on
                  Multiagent Systems},
  year =	 1995,
  abstract =	 {Distributed constraint optimization imposes
                  considerable complexity in agents' coordinated
                  search for an optimal solution. However, in many
                  application domains, problems often exhibit special
                  structures that can be exploited to facilitate more
                  efficient problem solving. One of the most recurrent
                  structures involves disparity among subproblems. We
                  present a coordination mechanism, Ascend,for
                  distributed constraint optimization that takes
                  advantage of disparity among subproblems to
                  efficiently guide distributed local search for
                  global optimality. The coordination mechanism
                  assigns different overlapping subproblems to agents
                  who must interact and iteratively converge on a
                  solution. In particular, an anchor agent who
                  conducts local best first search to optimize its
                  subsolution interacts with the rest of the agents
                  who perform distributed constraint satisfaction to
                  enforce problem constraints and constraints imposed
                  by the anchor agent. We focus our study on the
                  well-known NP-complete job shop scheduling
                  problem. We define and study two problem structure
                  measures, disparity ratio and disparity composition
                  ratio. We experimentally evaluated the effectiveness
                  of the Anchor&Ascend mechanism on a suite of job
                  shop scheduling problems over a wide range of values
                  of disparity composition. Our experimental results
                  show that (1) considerable advantagecan be obtained
                  by explicitly exploiting disparity (2) disparity
                  composition ratio plays a more important role than
                  disparity ratio in finding high quality solution
                  with little computational cost. },
  keywords =     {multiagent dcop},
  url =		 {http://jmvidal.cse.sc.edu/library/liu95a.pdf},
  cluster = 	 {17361906296120250554}
}