Index
Previous
Next
Theoretical Time Complexity
We define an
allocation
as an assignment of agents to services.
Having one service agent change its state corresponds to a move to a neighboring allocation
If we assume the utilities of neighboring allocations are independent then:
The number of local optima = |Agents|/2
b
where b is the branching factor.
The expected worst case distance from any allocation to the nearest local optima is proportional to b.
Jose M. Vidal
- University of South Carolina
7
TargetShare
03 August 2000, 10:01PM