More Like this

1. A General Framework for Approximating Min Sum Ordering Problems

   Happach, Felix; Hellerstein, Lisa; Lidbetter, Thomas (July 2020, ArXivorg)

   We consider a large family of problems in which an ordering (or, more precisely, a chain of subsets) of a finite set must be chosen to minimize some weighted sum of costs. This family includes variations of Min Sum Set Cover (MSSC), several scheduling and search problems, and problems in Boolean function evaluation. We define a new problem, called the Min Sum Ordering Problem (MSOP) which generalizes all these problems using a cost and a weight function on subsets of a finite set. Assuming a polynomial time α-approximation algorithm for the problem of finding a subset whose ratio of weight to cost is maximal, we show that under very minimal assumptions, there is a polynomial time 4α-approximation algorithm for MSOP. This approximation result generalizes a proof technique used for several distinct problems in the literature. We apply this to obtain a number of new approximation results. 

   more » « less
2. A family of models in support of realistic drug interdiction location decision‐making

   https://doi.org/10.1111/tgis.12921  

   Price, Ashleigh N.; Curtin, Kevin M.; Magliocca, Nicholas R.; Turner, Daniel; Mitchell, Penelope; McSweeney, Kendra; Summers, Diana L. (March 2022, Transactions in GIS)

   Abstract Long‐standing federal drug‐control policy aims to reduce the flow of narcotics into the USA, in part by intercepting cocaine shipments en route from South American production regions to North American consumer markets. Drug interdiction efforts operate over a large geographic area, containing complex drug trafficking networks in a dynamic environment. The extant interdiction models in the operations research and location science literature do not realistically model the objectives of and constraints on the interdiction forces, and therefore counterdrug organizations do not employ those models in their decision‐making processes. This article presents three new models built on the maximal covering location problem (MCLP): the maximal covering location problem for interdiction (MCLP‐I), multiple‐demand maximal covering location problem (MD‐MCLP), and multiple‐type maximal covering location problem (MT‐MCLP). These are novel formulations that permit multiple types of demands and facilities to be covered, and the utility of these formulations is demonstrated in the context of counterdrug operations. Optimal interdiction locations are determined within the geography of the Central American transit zone, using a coupled GIS and optimization framework. The results identify the optimal interdiction locations for known or estimated drug shipments and can constrain those optimal locations by differentiating among drug traffickers, the types of interdiction resources, and agency jurisdictions. This research both demonstrates the flexibility in designing alternative interdiction scenarios and presents novel covering models that may be extended to other application areas and operational contexts. 

   more » « less
3. Fair and Efficient Allocations of Chores under Bivalued Preferences

   https://doi.org/10.1609/aaai.v36i5.20436  

   Garg, Jugal; Murhekar, Aniket; Qin, John (June 2022, Proceedings of the AAAI Conference on Artificial Intelligence)

   We study the problem of fair and efficient allocation of a set of indivisible chores to agents with additive cost functions. We consider the popular fairness notion of envy-freeness up to one good (EF1) with the efficiency notion of Pareto-optimality (PO). While it is known that EF1+PO allocations exists and can be computed in pseudo-polynomial time in the case of goods, the same problem is open for chores. Our first result is a strongly polynomial-time algorithm for computing an EF1+PO allocation for bivalued instances, where agents have (at most) two disutility values for the chores. To the best of our knowledge, this is the first non-trivial class of chores to admit an EF1+PO allocation and an efficient algorithm for its computation. We also study the problem of computing an envy-free (EF) and PO allocation for the case of divisible chores. While the existence of EF+PO allocation is known via competitive equilibrium with equal incomes, its efficient computation is open. Our second result shows that for bivalued instances, an EF+PO allocation can be computed in strongly polynomial-time. 

   more » « less
4. Network Cost-Sharing Games: Equilibrium Computation and Applications to Election Modeling

   https://doi.org/10.1007/978-3-030-04651-4\_49  

   Swamy, Rahul; Murray, Timothy; Garg, Jugal (December 2018, Lecture notes in computer science)

   We introduce and study a variant of network cost-sharing games with additional non-shareable costs (NCSG+), which is shown to possess a pure Nash equilibrium (PNE). We extend polynomial-time PNE computation results to a class of graphs that generalizes series-parallel graphs when the non-shareable costs are player-independent. Further, an election game model is presented based on an NCSG+ when voter opinions form natural discrete clusters. This model captures several variants of the classic Hotelling-Downs election model, including ones with limited attraction, ability of candidates to enter, change stance positions and exit any time during the campaign or abstain from the race, the restriction on candidates to access certain stance positions, and the operational costs of running a campaign. Finally, we provide a polynomial-time PNE computation for an election game when stance changes are restricted. 

   more » « less
5. A Progressive Approximation Approach for the Exact Solution of Sparse Large-Scale Binary Interdiction Games

   https://doi.org/10.1287/ijoc.2021.1085  

   Contardo, Claudio; Sefair, Jorge A. (March 2022, INFORMS Journal on Computing)

   We present a progressive approximation algorithm for the exact solution of several classes of interdiction games in which two noncooperative players (namely an attacker and a follower) interact sequentially. The follower must solve an optimization problem that has been previously perturbed by means of a series of attacking actions led by the attacker. These attacking actions aim at augmenting the cost of the decision variables of the follower’s optimization problem. The objective, from the attacker’s viewpoint, is that of choosing an attacking strategy that reduces as much as possible the quality of the optimal solution attainable by the follower. The progressive approximation mechanism consists of the iterative solution of an interdiction problem in which the attacker actions are restricted to a subset of the whole solution space and a pricing subproblem invoked with the objective of proving the optimality of the attacking strategy. This scheme is especially useful when the optimal solutions to the follower’s subproblem intersect with the decision space of the attacker only in a small number of decision variables. In such cases, the progressive approximation method can solve interdiction games otherwise intractable for classical methods. We illustrate the efficiency of our approach on the shortest path, 0-1 knapsack and facility location interdiction games. Summary of Contribution: In this article, we present a progressive approximation algorithm for the exact solution of several classes of interdiction games in which two noncooperative players (namely an attacker and a follower) interact sequentially. We exploit the discrete nature of this interdiction game to design an effective algorithmic framework that improves the performance of general-purpose solvers. Our algorithm combines elements from mathematical programming and computer science, including a metaheuristic algorithm, a binary search procedure, a cutting-planes algorithm, and supervalid inequalities. Although we illustrate our results on three specific problems (shortest path, 0-1 knapsack, and facility location), our algorithmic framework can be extended to a broader class of interdiction problems. 

   more » « less