A number of combinatorial problems of interest to computational economists, such as some two-sided matching problems, belong to the complexity class NP. The best known solutions to these problems require exponential computation time in the size of the input, and are intractable in practice except for very small input size. We present an overview of a new distributed-computation technique called "nagging" that, while still exponential, allows one to harness multiple processors to extend the size of the largest solvable problem in a resource-bounded environment. Nagging requires relatively infrequent and brief interprocessor communication, is naturally tolerant (i.e., unaffected by the dynamic loss of processing elements), and exceptionally scalable in practice (i.e., robust in the presence of high message latencies, and, therefore, suitable for use in very large networks).
Download Info
To our knowledge, this item is not available for
download. To find whether it is available, there are three
options:
1. Check below under "Related research" whether another version of this item is available online.
2. Check on the provider's web page
whether it is in fact available.
3. Perform a search for a similarly titled item that would be
available.