Nelson A. Uhan

Abstract: We study the Maximum Flow Network Interdiction Problem (MFNIP). We present two classes of polynomially separable valid inequalities for Cardinality MFNIP. We also prove the integrality gap of the LP relaxation of Wood's (1993) integer program is not bounded by a constant factor, even when the LP relaxation is strengthened by our valid inequalities. Finally, we provide an approximation-factor-preserving reduction from the simpler R-Interdiction Covering Problem to MFNIP.

Abstract: In this work, we apply ideas from cooperative game theory to study situations in which a set of agents face supermodular costs. These situations appear in a variety of scheduling contexts, as well as in some settings related to facility location and network design. Intuitively, cooperation amongst rational agents who face supermodular costs is unlikely. However, in circumstances where the failure to cooperate may lead to negative externalities, one might be interested in methods of encouraging cooperation. In cooperative game theory, one indication that cooperation is achievable is the existence of an efficient and stable cost allocation. The least core value of a cooperative game is the minimum penalty we need to charge a coalition for acting independently that ensures the existence of an efficient and stable cost allocation. The set of all such cost allocations is called the least core. In this paper, we study the computational complexity and approximability of computing the least core value of supermodular cost cooperative games. We show that computing the least core value of supermodular cost cooperative games is strongly NP-hard, and build a framework to approximate the least core value of these games using oracles that approximately determine maximally violated constraints. This framework yields a (3+\epsilon)-approximation algorithm for computing the least core value of supermodular cost cooperative games. As a by-product, we show how to compute accompanying approximate least core cost allocations for these games. We also apply our approximation framework to obtain better results for two particular classes of supermodular cost cooperative games that arise from scheduling and matroid optimization.

Abstract: We study minimizing the sum of weighted completion times in a concurrent open shop environment. We show several interesting properties of various natural linear programming relaxations for this problem, including that they all have an integrality gap of 2. In addition, we propose a simple combinatorial 2-approximation algorithm that can be viewed as a primal-dual algorithm or a greedy algorithm that starts from the end of the schedule. Finally, we show that this problem is inapproximable within a factor of 6/5 - \epsilon (or within a factor 4/3 - \epsilon if the Unique Games Conjecture is true) for any \epsilon > 0, unless P = NP.

Abstract: We consider the problem of minimizing the weighted sum of completion times on a single machine subject to bipartite precedence constraints where all minimal jobs have unit processing time and zero weight, and all maximal jobs have zero processing time and unit weight. This NP-hard scheduling problem can be equivalently viewed as a graph orientation problem on a mixed complete bipartite graph. For various probability distributions over these instances--including the uniform distribution--we show several "almost all"-type results, including that for almost all instances, every feasible solution is arbitrarily close to optimal. To the best of our knowledge, our results are the first of their kind for scheduling and graph orientation problems.