A Caltech Library Service


Page, Scott E. (1993) Covers. Social Science Working Paper, 872. California Institute of Technology , Pasadena, CA. (Unpublished)

[img] PDF (sswp 872 - Dec. 1993) - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


This paper introduces the theory of covers for functions defined over binary variables. Covers formalize the notion of decomposability. Large complex problems are decomposed into subproblems each containing fewer variables, which can then be solved in parallel. Practical applications of the benefits from decomposition include the parallel architecture of supercomputers, the divisionalization of firms, and the decentralization of economic activity. In this introductory paper, we show how covers also shed light on the choice among public projects with complementarities. Further, covers provide a measure of complexity/decomposability with respect to contour sets, allowing for nonlinear effects which occur near the optimum to receive more weight than nonlinear effects arbitrarily located in the domain. Finally, as we demonstrate, covers can be used to analyze and to calibrate search algorithms.

Item Type:Report or Paper (Working Paper)
Additional Information:The author would like to thank Stan Reiter, David Richardson, and Jim Jordan for their insights.
Group:Social Science Working Papers
Series Name:Social Science Working Paper
Issue or Number:872
Record Number:CaltechAUTHORS:20170823-141457013
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:80739
Deposited By: Jacquelyn Bussone
Deposited On:28 Aug 2017 22:56
Last Modified:03 Oct 2019 18:34

Repository Staff Only: item control page