Hello! I'm Nelson Uhan.

I'm a Professor in the Mathematics Department at the United States Naval Academy.

At USNA, I teach a variety of courses, ranging from calculus to stochastic processes. Broadly speaking, my research interests are in mathematical optimization and game theory.

I received a PhD in operations research from MIT in 2008, and an AB and SM in applied mathematics from Harvard University in 2002. My mathematical genealogy can be found here. My Erdös number is 3.

 

  Mathematics Department
United States Naval Academy
Chauvenet Hall
572C Holloway Road
Annapolis, MD 21402
USA

  uhan at usna dot edu

 

Teaching

Courses taught

At USNA

Applied Statistics (SM339)
Spring 2023, Spring 2024
description   website
Interval estimation, hypothesis testing. Linear regression. Logistic regression.
Operations Research Capstone (SA475)
Spring 2014, Spring 2015, Spring 2016, Spring 2018, Spring 2022, Spring 2023, Spring 2024
description   website
Students work in teams on a semester-long real-world project involving the application of operations research and statistical methods. Topics and external collaborators change from semester to semester.
Dynamic and Stochastic Models (SA402)
Fall 2013, Fall 2016, Fall 2019, Fall 2022, Fall 2023
description   website
This course provides an introduction to modeling and analyzing systems that evolve dynamically over time and whose behavior is stochastic, or uncertain. This course focuses on models that are amenable to mathematical analysis, while using basic notions from simulation to develop intuition.
Mathematical Models for Decision Making (SA367)
Spring 2017, Spring 2018, Spring 2020, Spring 2021, Spring 2022
description   website
This course provides an alternative introduction to operations research models. In particular, this course focuses on (i) modeling real-world decision-making problems as shortest path problems, deterministic dynamic programs, and stochastic dynamic programs, (i) solving these models with computational tools and (iii) interpreting their output.
Data Wrangling and Visualization (SA463A)
Fall 2020, Fall 2021
description   website
In this course, students will learn to use Python to wrangle large, messy data sets into forms suitable for modeling and analysis, and create visualizations that provide useful insights for decision making.
Calculus III with Optimization (SM223)
Fall 2012, Fall 2017, Fall 2020, Fall 2021
description   website
Differential and integral calculus of several real variables. Vector analysis. Optimization techniques for functions of several variables.
Linear Programming (SA305)
Spring 2013, Spring 2014, Spring 2015, Spring 2016, Spring 2021
description   website
Operations research (OR) is a broad field which, loosely speaking, investigates how mathematical techniques can be used to solve "real-life" decision-making problems. This course provides an introduction to linear programming, a fundamental technique used in OR. In particular, the course focuses on formulating mathematical optimization models (also called mathematical programs), and understanding the mathematical underpinnings of linear programming algorithms.
Introduction to Applied Mathematics with Python (SM286D)
Spring 2020
description   website
An introduction to solving problems in applied mathematics and operations research using computer programming; in particular, using the Python programming language.
Mathematical Methods for Economics (SM275)
Fall 2015, Fall 2019
description   website
A brief introduction to linear algebra, differential and difference equations, and nonlinear optimization for economics majors.
Simulation Modeling (SA421)
Spring 2013, Fall 2014, Fall 2015, Fall 2017
description   website
This course focuses on the use of simulation as a decision-making tool, including explorations into what simulation is, how to use it, and when its use is appropriate. These topics are studied using R and JaamSim, an open source discrete-event simulation software.

At Purdue

Operations Research - Optimization (IE 335)
Fall 2008, Fall 2009, Spring 2010, Fall 2010, Spring 2011, Fall 2011, Spring 2012
description
An introduction to optimization for undergraduate engineering students, primarily juniors majoring in industrial engineering. Linear, network, and discrete optimization models and algorithms.
Integer Programming (IE 634)
Fall 2011
description
A graduate-level course in integer programming. Review of linear progamming and polyhedral theory. Valid inequalities, facet-defining inequalities, ideal formulations. Integer programming duality. Branch and bound, cutting plane methods, column generation methods.
Combinatorial Optimization (IE 639)
Fall 2010
description
A graduate-level course in combinatorial optimization. Minimum spanning trees, shortest paths, maximum flows and minimum cuts. Polyhedral theory and linear programming duality. Matroids and submodularity. Matchings.

Students supervised

At USNA

  • Joshua Douberly, BS in operations research with honors, 2023
  • George Gilliam, BS in mathematics with honors, 2020
  • Stephen Ward, BS in operations research, 2017
    Supervised Bowman Scholar project with Jay Foraker.

At Purdue

  • Kan Fang, PhD in industrial engineering, December 2013
  • Jikai Zou, MS in industrial engineering, May 2013
  • Sindhura Balireddi, MS in computer science, August 2010
  • Mohan Gopaladesikan, MS in industrial engineering, August 2010

Teaching Materials and Software

If you find any of these materials useful, please let me know!

Guided notes

You can find guided lesson notes for most of the courses I have taught at USNA on the course websites linked above. Check the Lessons sections of those web pages.

Interactive examples

This Jupyter notebook executes and shows each step of the simplex method using Dantzig's rule, as described in [D. J. Rader (2010). Deterministic Operations Research: Models and Algorithms. Wiley.]

These interactive examples in Jupyter notebooks can be suitable for an undergraduate course in stochastic processes:

GMPL / MathProg

GMPL Notebook allows you to write and solve GMPL/MathProg models in a Jupyter notebook. It serves as a nice interactive learning enivronment for GMPL.

GMPL Magic is a set of IPython/Jupyter magics that lets you mix GMPL/MathProg code and output with other languages (for example, Python) in an IPython session or a Jupyter notebook.

Research

Publications

Bibliographic profiles

Journal articles

Approximating a linear multiplicative objective in watershed management optimization
A. N. Boddiford, D. E. Kaufman, D. E. Skipper, N. A. Uhan
European Journal of Operational Research, accepted for publication, June 2022
abstract   paper
Abstract. Implementing management practices in a cost-efficient manner is critical for regional efforts to reduce the amount of pollutants entering the Chesapeake Bay. We study the problem of selecting a subset of practices that minimizes pollutant load—subject to budgetary and environmental constraints—as simulated in a widely used regulatory watershed model. Mimicking the computation of pollutant load in the regulatory model, we formulate this problem as a continuous optimization model with a linear multiplicative objective function and linear constraints. To lay the groundwork for incorporating additional stakeholder requirements in the future, especially those that would require integer variables, we present and study a continuous linear optimization model that approximates the nonlinear model. The linear model, which requires an exponential number of variables, arises naturally as an alternative model for the same underlying physical process. We examine the theoretical behavior of these optimization models and investigate restrictions of the linear model to handle its large number of variables. Through extensive computational tests on real and randomly generated instances, we demonstrate that the linear model and its restrictions provide optimal solutions close to those of the nonlinear model in practice, despite poor approximation properties in the worst case. We conclude that the linear modeltogether with our approach to handling its large number of variablesprovides a viable framework from which to extend the optimization model to better meet the needs of the Chesapeake Bay watershed management stakeholders.
Acyclic mechanism design for freight consolidation
W. Zhang, N. A. Uhan, M. Dessouky, A. Toriello
Transportation Science 56(3): 571-584, 2022
abstract   paper
Abstract. Freight consolidation is a logistics practice that improves the cost-effectiveness and efficiency of transportation operations, and also reduces energy consumption and carbon footprint. A "fair" shipping cost sharing scheme is indispensable to help establish and sustain the cooperation of a group of suppliers in freight consolidation. In this paper, we design a truthful acyclic mechanism to solve the cost-sharing problem in a freight consolidation system with one consolidation center and one common destination. Applying the acyclic mechanism, the consolidation center decides which suppliers' demands ship via the consolidation center and their corresponding cost shares based on their willingness to pay for the service. The proposed acyclic mechanism is designed based on bin packing solutions that are also strong Nash equilibria for a related non-cooperative game. We study the budget-balance of the mechanism both theoretically and numerically. We prove a 2-budget-balance guarantee for the mechanism in general and better budget-balance guarantees under specific problem settings. Empirical tests on budget-balance show that the mechanism only charges slightly more than the minimum shipping cost in practice. We also study the economic efficiency of our mechanism numerically to investigate its impact on social welfare under different conditions.
Computing payoff allocations in the approximate core of linear programming games in a privacy-preserving manner
G. Gilliam, N. A. Uhan
Operations Research Letters 50(1): 64-71, 2022
abstract   paper
Abstract. We investigate privacy-preserving ways of allocating payoffs among players participating in a joint venture, using tools from cooperative game theory and differential privacy. In particular, we examine linear programming games, an important class of cooperative games that model a myriad of payoff sharing problems, including those from logistics and network design. We show that we can compute a payoff allocation in the approximate core of these games in a way that satisfies joint differential privacy.
Cost-sharing mechanism design for ride-sharing
S. Hu, M. Dessouky, N. A. Uhan, P. Vayanos
Transportation Research Part B: Methodological 150:410-434, 2021
abstract   paper
Abstract. In this paper, we focus on the cost-sharing problem for ride-sharing: determining how to allocate the total ride cost between the driver and the passengers. In particular, we focus on the scenario where drivers are also commuters with the goal of cost recovery. We identify the properties that a desirable cost-sharing mechanism should have and develop a general framework that can be used to create specific cost-sharing mechanisms. We propose specific mechanisms and analyze their relative advantages and disadvantages so that service providers can select a mechanism according to their different needs. In addition, we incorporate the value of time by allowing passengers to have inconvenience costs due to extra travel time caused by detours for picking up the passengers, and provide discount methods to compensate for these costs. We evaluate our approach using real traffic data from the downtown Los Angeles area. Our results show that each proposed mechanism has its unique advantages and that the discount methods can successfully reduce the number of no-passenger vehicles for a large ride-sharing system.
Equilibrium strategies for multiple interdictors on a common network
H. Sreekumaran, A. R. Hota, A. L. Liu, N. A. Uhan, S. Sundaram
European Journal of Operational Research 288(2): 523-538, 2021
abstract   paper
Abstract. In this work, we introduce multi-interdictor games, which model interactions among multiple interdictors with differing objectives operating on a common network. As a starting point, we focus on shortest path multi-interdictor (SPMI) games, where multiple interdictors try to increase the shortest path lengths of their own adversaries attempting to traverse a common network. We first establish results regarding the existence of equilibria for SPMI games under both discrete and continuous interdiction strategies. To compute such an equilibrium, we present a reformulation of the SPMI game, which leads to a generalized Nash equilibrium problem (GNEP) with non-shared constraints. While such a problem is computationally challenging in general, we show that under continuous interdiction actions, a SPMI game can be formulated as a linear complementarity problem and solved by Lemke's algorithm. In addition, we present decentralized heuristic algorithms based on best response dynamics for games under both continuous and discrete interdiction strategies. Finally, we establish theoretical lower bounds on the worst-case efficiency loss of equilibria in SPMI games, with such loss caused by the lack of coordination among noncooperative interdictors, and use the decentralized algorithms to numerically study the average-case efficiency loss.
Linear programming models: identifying common errors in college engineering students' work with complex word problems
R. H. Kenney, T. An, S.-H. Kim, N. A. Uhan, J. S. Yi, A. Shamsul
International Journal of Science and Mathematics Education 18: 635-655, 2020
abstract   paper
Abstract. In linear programming, many students find modeling — translating a verbal description of a problem into a valid mathematical expression — difficult to learn. To better understand this, we examine the existing characteristics of college engineering students' errors across linear programming modeling word problems. We examined textbooks to identify the types of modeling problems typically found in introductory linear programming courses. We then developed a comprehensive set of tasks and analyzed students' work to create a taxonomy of the errors and issues that students exhibited. From our findings, we define four categories of identified error types: (1) decision variable errors, (2) variable relationship errors, (3) notation errors, and (4) form errors. This study contributes to the research by investigating students' work in an area of undergraduate mathematics that has not been heavily explored before. Findings suggest specific areas of focus for future work in helping students develop their understanding of linear programming models, and mathematical modeling in word problems in general.
Moulin mechanism design for freight consolidation
W. Zhang, N. A. Uhan, M. Dessouky, A. Toriello
Transportation Research Part B: Methodological 116: 141-162, 2018
abstract   paper
Abstract. A fair cost allocation scheme is critical for forming and sustaining horizontal cooperation that leads to cost reductions. In order to incentivize suppliers to cooperate in freight consolidation, we design a cost-sharing mechanism to solve a cost allocation problem arising in freight consolidation among small suppliers: that is, suppliers whose total demand fits into one truckload. This cost-sharing mechanism determines the set of suppliers who will participate in the consolidation and their corresponding cost shares. We design this cost-sharing mechanism to ensure that every supplier is willing to reveal their preference truthfully and the total consolidation cost incurred is recovered by the allocated costs. Moreover, our analytical and numerical study shows that our cost-sharing mechanism often yields cost shares that maximize the social welfare of all the suppliers.
Resilient course and instructor scheduling in the Mathematics Department at the United States Naval Academy
S. J. Ward, J. Foraker, N. A. Uhan
Military Operations Research 23(3): 21-45, 2018
abstract   paper
Abstract. In this work, we study the problem of scheduling courses and instructors in the Mathematics Department at the United States Naval Academy (USNA) in a resilient manner. Every semester, the department needs to schedule around 70 instructors and 150-180 course sections into 30 class periods and 30 rooms. We formulate a stochastic integer linear program that schedules these courses, instructors, and rooms. In addition to maximizing instructor preferences and room stability, this stochastic integer linear program minimizes the expected number of changes required in the schedule if a disruption were to occur, given a subjective probability distribution over a finite set of possible disruption scenarios. We run our model on a number of instances derived from actual data from the past three years, and investigate the effect of emphasizing different parts of the objective function on the running time and resulting schedules.
Dynamic linear programming games with risk-averse players
A. Toriello, N. A. Uhan
Mathematical Programming 163(1): 25-56, 2017
abstract   paper
Abstract. Motivated by situations in which independent agents wish to cooperate in some uncertain endeavor over time, we study dynamic linear programming games, which generalize classical linear production games to multi-period settings under uncertainty. We specifically consider that players may have risk-averse attitudes towards uncertainty, and model this risk aversion using coherent conditional risk measures. For this setting, we study the strong sequential core, a natural extension of the core to dynamic settings. We characterize the strong sequential core as the set of allocations that satisfy a particular finite set of inequalities that depend on an auxiliary optimization model, and then leverage this characterization to establish sufficient conditions for emptiness and non-emptiness. Qualitatively, whereas the strong sequential core is always non-empty when players are risk-neutral, our results indicate that cooperation in the presence of risk aversion is much more difficult. We illustrate this with an application to cooperative newsvendor games, where we find that cooperation is possible when it least benefits players, and may be impossible when it offers more benefit.
Scheduling on a single machine under time-of-use tariffs
K. Fang, N. A. Uhan, F. Zhao, J. W. Sutherland
Annals of Operations Research 238(1): 199-227, 2016
abstract   paper
Abstract. We consider the problem of scheduling jobs on a single machine to minimize the total electricity cost of processing these jobs under time-of-use electricity tariffs. For the uniform-speed case, in which all jobs have arbitrary power demands and must be processed at a single uniform speed, we prove that the non-preemptive version of this problem is inapproximable within a constant factor unless P = NP. On the other hand, when all the jobs have the same workload and the electricity prices follow a so-called pyramidal structure, we show that this problem can be solved in polynomial time. For the speed-scalable case, in which jobs can be processed at an arbitrary speed with a trade-off between speed and power demand, we show that the non-preemptive version of the problem is strongly NP-hard. We also present different approximation algorithms for this case, and test the computational performance of these approximation algorithms on randomly generated instances. In addition, for both the uniform-speed and speed-scaling cases, we show how to compute optimal schedules for the preemptive version of the problem in polynomial time.
Stochastic linear programming games with concave preferences
N. A. Uhan
European Journal of Operational Research 243(2): 637-646, 2015
abstract   paper
Abstract. We study stochastic linear programming games: a class of stochastic cooperative games whose payoffs under any realization of uncertainty are determined by a specially structured linear program. These games can model a variety of settings, including inventory centralization and cooperative network fortification. We focus on the core of these games under an allocation scheme that determines how payoffs are distributed before the uncertainty is realized, and allows for arbitrarily different distributions for each realization of the uncertainty. Assuming that each player's preferences over random payoffs are represented by a concave monetary utility functional, we prove that these games have a nonempty core. Furthermore, by establishing a connection between stochastic linear programming games, linear programming games and linear semi-infinite programming games, we show that an allocation in the core can be computed efficiently under some circumstances.
Dynamic cost allocation for economic lot sizing games
A. Toriello, N. A. Uhan
Operations Research Letters 42(1) 82-84, 2014
abstract   paper
Abstract. We consider a cooperative game defined by an economic lot sizing problem with concave ordering costs over a finite time horizon, in which each player faces demand for a single product in each period and coalitions can pool orders. We show how to compute a dynamic cost allocation in the strong sequential core of this game, i.e. an allocation over time that exactly distributes costs and is stable against coalitional defections at every period of the time horizon.
The complexity of egalitarian mechanisms for linear programming games
N. A. Uhan
Operations Research Letters 42(1) 76-81, 2014
abstract   paper
Abstract. We show that the most cost-efficient subset problem for linear programming games is NP-hard, and in fact inapproximable within a constant factor in polynomial time, unless P = NP. This in turn implies that computing the prices output by an egalitarian mechanism and computing a cost allocation in the equal split-off set for linear programming games is NP-hard.
POETIC: interactive solutions to alleviate the reversal error in student-professor type problems
S.-H. Kim, D. Phang, T. An, J. S. Yi, R. H. Kenney, N. A. Uhan
International Journal of Human-Computer Studies 72(1) 12-22, 2014
abstract   paper
Abstract. The reversal error — reversing the relationship between two variables in a mathematical word problem — is a long-standing issue in mathematics education, despite its apparent simplicity. In this paper, we describe and study POETIC, an interactive web-based environment we developed to teach users to avoid the reversal error. POETIC uses two types of novel interactive visualization, which we call the Test-Case and Room-Metaphor approaches. To verify the effectiveness of these approaches, we conducted crowdsourcing-based comparison studies with 200 participants and found that both the Test-Case and Room-Metaphor approaches significantly decreased the frequency of reversal errors for certain types of word problems. Our results show that interactive visualization of equations can reduce the occurrence of the reversal error.
On traveling salesman games with asymmetric costs
A. Toriello, N. A. Uhan
Operations Research 61(6) 1429-1434, 2013
abstract   paper
Abstract. We consider cooperative traveling salesman games with non-negative asymmetric costs satisfying the triangle inequality. We construct a stable cost allocation with budget balance guarantee equal to the Held-Karp integrality gap for the asymmetric traveling salesman problem, using the parsimonious property and a previously unknown connection to linear production games. We also show that our techniques extend to larger classes of network design games. We then provide a simple example showing that our cost allocation does not necessarily achieve the best possible budget balance guarantee, even among cost allocations stable for the game defined by the Held-Karp relaxation, and discuss its implications on future work on traveling salesman games.
Flow shop scheduling with peak power consumption constraints
K. Fang, N. A. Uhan, F. Zhao, J. W. Sutherland
Annals of Operations Research 206(1) 115-145, 2013
abstract   paper
Abstract. We study scheduling as a means to address the increasing energy concerns in manufacturing enterprises. In particular, we consider a flow shop scheduling problem with a restriction on peak power consumption, in addition to the traditional time-based objectives. We investigate both mathematical programming and combinatorial approaches to this scheduling problem, and test our approaches with instances arising from the manufacturing of cast iron plates.
Approximating the least core value and least core of cooperative games with supermodular costs
A. S. Schulz, N. A. Uhan
Discrete Optimization 10(2) 163-180, 2013
abstract   paper
Abstract. We study the approximation of the least core value and the least core of supermodular cost cooperative games. We provide a framework for approximation based on 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, and a polynomial-time algorithm for computing a cost allocation in the 2-approximate least core of these games. This approximation framework extends naturally to submodular profit cooperative games. For scheduling games, a special class of supermodular cost cooperative games, we give a fully polynomial-time approximation scheme for computing the least core value. For matroid profit games, a special class of submodular profit cooperative games, we give exact polynomial-time algorithms for computing the least core value as well as a least core cost allocation.
A primal-dual algorithm for computing a cost allocation in the core of economic lot-sizing games
M. Gopaladesikan, N. A. Uhan, J. Zou
Operations Research Letters 40(6) 453-458, 2012
abstract   paper
Abstract. We consider the economic lot-sizing game with general concave ordering cost functions. It is well-known that the core of this game is nonempty when the inventory holding costs are linear. The main contribution of this work is a combinatorial, primal-dual algorithm that computes a cost allocation in the core of these games in polynomial time. We also show that this algorithm can be used to compute a cost allocation in the core of economic lot-sizing games with remanufacturing under certain assumptions.
The impact of group purchasing organizations on healthcare-product supply chains
Q. Hu, L. B. Schwarz, N. A. Uhan
Manufacturing & Service Operations Management 14(1) 7-23, 2012
abstract   paper
Abstract. This paper examines the impact of group purchasing organizations (GPOs) on healthcare-product supply chains. The supply chain we study consists of a profit-maximizing manufacturer with a quantity-discount schedule that is nonincreasing in quantity and ensures nondecreasing revenue, a profit-maximizing GPO, a competitive source selling at a fixed unit price, and n providers (e.g., hospitals) with fixed demands for a single product. Each provider seeks to minimize its total purchasing cost (i.e., the cost of the goods plus the provider's own fixed transaction cost). Buying through the GPO offers providers possible cost reductions, but may involve a membership fee. Selling through the GPO offers the manufacturer possibly higher volumes, but requires that the manufacturer pay the GPO a contract administration fee (CAF); i.e., a percentage of all revenue contracted through it. Using a game-theoretic model, we examine questions about this supply chain, including how the presence of a GPO affects the providers' total purchasing costs. We also address the controversy about whether Congress should amend the Social Security Act, which, under current law, permits CAFs. Among other things, we conclude that although CAFs affect the distribution of profits between manufacturers and GPOs, they do not affect the providers' total purchasing costs.
Diversification of fuel costs accounting for load variation
S. Ruangpattana, P. V. Preckel, D. J. Gotham, K. Muthuraman, M. Velástegui, T. L. Morin, N. A. Uhan
Energy Policy 42 400-408, 2012
abstract   paper
Abstract. A practical mathematical programming model for the strategic fuel diversification problem is presented. The model is designed to consider the tradeoffs between the expected costs of investments in capacity, operating and maintenance costs, average fuel costs, and the variability of fuel costs. In addition, the model is designed to take the load curve into account at a high degree of resolution, while keeping the computational burden at a practical level. The model is illustrated with a case study for Indiana's power generation system. The model reveals that an effective means of reducing the volatility of the system-level fuel costs is through the reduction of dependence on coal-fired generation with an attendant shift towards nuclear generation. Model results indicate that about a 25% reduction in the standard deviation of the generation costs can be achieved with about a 20%-25% increase in average fuel costs. Scenarios that incorporate costs for carbon dioxide emissions or a moratorium on nuclear capacity additions are also presented.
Cost sharing mechanisms for scheduling under general demand settings
S. Balireddi, N. A. Uhan
European Journal of Operational Research 217(2) 270-277, 2012
abstract   paper
Abstract. We investigate cost-sharing mechanisms for scheduling cost-sharing games. We assume that the demand is general—that is, each player can be allocated one of several levels of service. We show how to design mechanisms for these games that are weakly group strategyproof, approximately budget-balanced, and approximately efficient, using approximation algorithms for the underlying scheduling problems. We consider scheduling cost-sharing games in single machine, parallel machine, and concurrent open shop environments.
A new approach to scheduling in manufacturing for power consumption and carbon footprint reduction
K. Fang, N. A. Uhan, F. Zhao, J. W. Sutherland
Journal of Manufacturing Systems 30(4) 234-240, 2011
Special issue, "Selected Papers of 39th North American Manufacturing Research Conference"
abstract   paper
Abstract. Manufacturing scheduling strategies have historically emphasized cycle time; in almost all cases, energy and environmental factors have not been considered in scheduling. This paper presents a new mathematical programming model of the flow shop scheduling problem that considers peak power load, energy consumption, and associated carbon footprint in addition to cycle time. The new model is demonstrated using a simple case study: a flow shop where two machines are employed to produce a variety of parts. In addition to the processing order of the jobs, the proposed scheduling problem considers the operation speed as an independent variable, which can be changed to affect the peak load and energy consumption. Even with a single objective, finding an optimal schedule is notoriously difficult, so directly applying commercial software to this multi-objective scheduling problem requires significant computation time. This paper calls for the development of more specialized algorithms for this new scheduling problem and examines computationally tractable approaches for finding near-optimal schedules.
Near-optimal solutions and integrality gaps for almost all instances of single-machine precedence-constrained scheduling
A. S. Schulz, N. A. Uhan
Mathematics of Operations Research 36(1) 14-23, 2011
abstract   paper
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.
Minimizing the weighted sum of completion times in concurrent open shops
M. Mastrolilli, M. Queyranne, A. S. Schulz, O. Svensson, N. A. Uhan
Operations Research Letters 38(5) 390-395, 2010
abstract   paper
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.
Sharing supermodular costs
A. S. Schulz, N. A. Uhan
Operations Research 58(4) 1051-1056, 2010
abstract   paper
Abstract. We study cooperative games with supermodular costs. We show that supermodular costs arise in a variety of situations: in particular, we show that the problem of minimizing a linear function over a supermodular polyhedron—a problem that often arises in combinatorial optimization—has supermodular optimal costs. In addition, we examine the computational complexity of the least core and least core value of supermodular cost cooperative games. We show that the problem of computing the least core value of these games is strongly NP-hard, and in fact, is inapproximable within a factor strictly less than 17/16 unless P = NP. For a particular class of supermodular cost cooperative games that arises from a scheduling problem, we show that the Shapley value—which, in this case, is computable in polynomial time—is in the least core, while computing the least core value is NP-hard.
The maximum flow network interdiction problem: valid inequalities, integrality gaps, and approximability
D. S. Altner, Ö. Ergun, N. A. Uhan
Operations Research Letters 38(1) 33-38, 2010
abstract   paper
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.

PhD Thesis

Algorithmic and Game-Theoretic Perspectives on Scheduling
N. A. Uhan
PhD Thesis, Operations Research Center, Massachusetts Institute of Technology, 2008
thesis