The Combinatorial Public Projects Problem (CPPP) is an abstraction of resource allocation problems in which agents have preferences over alternatives, and an outcome that is to be collectively shared by the agents is chosen so as to maximize the social welfare. We explore CPPP from both computational perspective and a mechanism design perspective. We examine CPPP in the hierarchy of complement free (subadditive) valuation classes and present positive and negative results for both unrestricted and truthful algorithms.

The existence of incentive-compatible, computationally-efficient mechanisms for combinatorial auctions with good approximation ratios is the paradigmatic problem in algorithmic mechanism design. It is believed that, in many cases, good approximations for combinatorial auctions may be unattainable due to an inherent clash between truthfulness and computational efficiency. In this paper, we prove the first computational-complexity inapproximability results for incentive-compatible mechanisms for combinatorial auctions. Our results are tight, hold for the important class of VCG-based mechanisms, and are based on the complexity assumption that NP has no polynomial-size circuits. We show two different techniques to obtain such lower bounds: one for deterministic mechanisms that attains optimal dependence on the number of players and number of items, and one that also applies to a class of randomized mechanisms and attains optimal dependence on the number of players. Both techniques are based on novel VC dimension machinery.

We consider the problem of minimizing the number of ADMs for single-source multicast communication in WDM rings using traffic grooming. We examine two distinct models of communication, one permitting the same message to be sent on multiple distinct wavelengths and one each message to be sent exactly once. The problem of minimizing the number of ADMs is shown to be NP-complete in the strong sense for both models. However, we are able to solve a special case in polynomial time and provide good approximation algorithms and heuristics for the remaining cases. These approximation algorithms and heuristics are validated both theoretically and experimentally.