We study succinct approximation of functions that have noisy oracle access. Namely, construction of a succinct representation of a function, given oracle access to an L-approximation of the function, rather than to the function itself. Specifically, we consider the question of the succinct representation of an approximation of a convex function v that cannot be … Read more
We study an incremental network design problem, where in each time period of the planning horizon an arc can be added to the network and a maximum flow problem is solved, and where the objective is to maximize the cumulative flow over the entire planning horizon. After presenting two mixed integer programming (MIP) formulations for … Read more
In 1976, Coffman and Sethi conjectured that a natural extension of LPT list scheduling to the bicriteria scheduling problem of minimizing makespan over flowtime optimal schedules, called LD algorithm, has a simple worst-case performance bound: (5m-2)/(4m-1) , where m is the number of machines. We study structure of potential minimal counterexamples to this conjecture and … Read more
We study the approximability of the classical quadratic knapsack problem (QKP) on special graph classes. In this case the quadratic terms of the objective function are not given for each pair of knapsack items. Instead an edge weighted graph G = (V,E) whose vertices represent the knapsack items induces a quadratic profit p_ij for the … Read more
In the \emph{incremental knapsack problem} ($\IK$), we are given a knapsack whose capacity grows weakly as a function of time. There is a time horizon of $T$ periods and the capacity of the knapsack is $B_t$ in period $t$ for $t = 1, \ldots, T$. We are also given a set $S$ of $N$ items … Read more
We present a framework for obtaining Fully Polynomial Time Approximation Schemes (FPTASs) for stochastic univariate dynamic programs with either convex or monotone single-period cost functions. This framework is developed through the establishment of two sets of computational rules, namely the Calculus of K-approximation Functions and the Calculus of K-approximation Sets. Using our framework, we provide … Read more
We consider the problem of scheduling on uniform processors with nonsimultaneous machine available times with the purpose of mini\-mi\-zing the maximum completion time. We give a variant of the Multifit algorithm which generates schedules which end within $1.382$ times the optimal maximum completion times. This results from properties of the Multifit algorithm when used for … Read more
Assortment optimization is an important problem that arises in many practical applications such as retailing and online advertising. In an assortment optimization problem, the goal is to select a subset of items that maximizes the expected revenue in the presence of the substitution behavior of consumers specified by a choice model. In this paper, we … Read more
The $pq$-relaxation for the pooling problem can be constructed by applying McCormick envelopes for each of the bilinear terms appearing in the so-called $pq$-formulation of the pooling problem. This relaxation can be strengthened by using piecewise-linear functions that over- and under-estimate each bilinear term. The resulting relaxation can be written as a mixed integer linear … Read more
We describe the generalization of Hazan’s algorithm for symmetric programming problems CitationNotre Dame Report, December, 2012ArticleDownload View PDF