Deciding 1-sovability of distributed task is NP-hard.
Ofer BiranShlomo MoranShmuel ZaksPublished in: WG (1990)
Keyphrases
- np hard
- optimal solution
- cooperative
- distributed systems
- closely related
- distributed environment
- peer to peer
- databases
- distributed data
- constraint satisfaction problems
- worst case
- lower bound
- multi agent
- genetic algorithm
- real world
- special case
- decision trees
- linear programming
- lightweight
- decision making
- decision problems
- knapsack problem
- database
- np hardness
- approximation ratio
- remains np hard