We propose two new fully polynomial-time approximation schemes for maximizing the weighted number of just-in-time jobs in a multi-machine proportionate flow shop. Both are set up using recently proposed frameworks for the construction of this type of approximation schemes for monotone dynamic programming formulations, and are faster by a linear factor with respect to the number of jobs, up to log terms, compared to the state-of-the-art fully polynomial-time approximation scheme for the problem.

We design a framework to obtain Fully Polynomial Time Approximation Schemes (FPTASes) for adjustable robust multistage decision making under the budgeted uncertainty sets introduced by Bertsimas and Sim. We apply this framework to the robust counterpart of three problems coming from operations research: (i) ordered knapsack, (ii) single-item inventory control, and (iii) single-item batch dispatch. Our work gives the first FPTAS for these problems, and for adjustable robust multistage decision making in general. The proposed approximation schemes are constructed with the technique of K-approximation sets and functions, relying on careful robust dynamic programming formulations for a master problem (corresponding to the decision maker) and for an adversary problem (corresponding to nature, which chooses bad realizations of uncertainty for the decision maker). The resulting algorithms are short and simple, requiring just a few concise subroutines. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: This research was supported in part by the United States-Israel Binational Science foundation [Grant 2018095). N. Halman was also supported in part by the Israel Science Foundation [Grants 399/17 and 1074/21].

In this paper we go one step further in the automatic generation of FPTASes for multistage stochastic dynamic programs with scalar state and action spaces, in which the cost-to-go functions have a monotone structure in the state variable. While there exist a few frameworks for automatic generation of FPTASes, so far none of them is general and simple enough to be extensively used. We believe that our framework has these two attributes and has great potential to attract interest from both the operations research and theoretical computer science communities. Moreover, it seems very reasonable that many intractable problems that currently do not admit an FPTAS, can be formulated as DPs that fit into our framework and therefore will admit a first FPTAS. Our results are achieved by a combination of Bellman equation formulations, the technique of $K$-approximation sets and functions, and in particular the calculus of $K$-approximation functions.

In this paper, we address two models of nondeterministic discrete time finite-horizon dynamic programs (DPs): implicit stochastic DPs (the information about the random events is given by value oracles to their cumulative distribution functions) and sample-based DPs (the information about the random events is deduced by drawing random samples). Such data-driven models frequently appear in practice, where the cumulative distribution functions of the underlying random variables are either unavailable or too complicated to work with. In both models, the single-period cost functions are accessed via value oracle calls and assumed to possess either monotone or convex structure. We develop the first near-optimal relative approximation schemes for each of the two models. Applications in stochastic inventory control (that is, several variants of the so-called newsvendor problem) are discussed in detail. Our results are achieved by a combination of Bellman equation calculations, density estimation results, and extensions of the technique of K-approximation sets and functions introduced by Halman et al. (2009) [Halman N, Klabjan D, Mostagir M, Orlin J, Simchi-Levi D (2009) A fully polynomial time approximation scheme for single-item stochastic inventory control with discrete demand. Math. Oper. Res. 34(3):674–685.].

Given n elements with nonnegative integer weights w=(w_1,...,w_n), an integer capacity C and positive integer ranges u=(u_1,...,u_n), we consider the counting version of the classic integer knapsack problem: find the number of distinct multisets whose weights add up to at most C. We give a deterministic algorithm that estimates the number of solutions to within relative error epsilon in time polynomial in n, log U and 1/epsilon, where U=max_i u_i. More precisely, our algorithm runs in O((n^3 log^2 U)/epsilon) log (n log U)/epsilon) time. This is an improvement of n^2 and 1/epsilon (up to log terms) over the best known deterministic algorithm by Gopalan et al. [FOCS, (2011), pp. 817-826]. Our algorithm is relatively simple, and its analysis is rather elementary. Our results are achieved by means of a careful formulation of the problem as a dynamic program, using the notion of binding constraints.

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 the first FPTASs for several NP-hard problems in various fields of research such as knapsack models, logistics, operations management, economics, and mathematical finance. Extensions of our framework via the use of the newly established computational rules are also discussed.

Helly's theorem says that, if every $d+1$ elements of a given finite set of convex objects in $\mathbb{R}^d$ have a common point, there is a point common to all of the objects in the set. In discrete Helly theorems the common point should belong to an a priori given set. In lexicographic Helly theorems the common point should not be lexicographically greater than a given point. Using discrete and lexicographic Helly theorems we get linear time solutions for various optimization problems. For this, we introduce the DLP-type (discrete linear programming–type) model, and provide new algorithms that solve in randomized linear time fixed-dimensional DLP-type problems. For variable-dimensional DLP-type problems, our algorithms run in time subexponential in the combinatorial dimension. Finally, we use our results in order to solve in randomized linear time problems such as the discrete p-center on the real line, the discrete weighted 1-center problem in $\mathbb{R}^d$ with either $l_1$ or $l_\infty$ norm, the standard (continuous) problem of finding a line transversal for a totally separable set of planar convex objects, a discrete version of the problem of finding a line transversal for a set of axis-parallel planar rectangles, and the (planar) lexicographic rectilinear p-center problem for $p=1,2,3$. These are the first known linear time algorithms for these problems. Moreover, we use our algorithms to solve in randomized subexponential time various problems in game theory, improving upon the best known algorithms for these problems.

Helly's theorem says that if every d + 1 elements of a given finite set of convex objects in /spl Ropf//sup d/ have a common point, then there is a point common to all of the objects in the set. We define three types of Helly theorems: discrete Helly theorems - where the common point should belong to an a-priori given set, lexicographic Helly theorems - where the common point should not be lexicographically greater than a given point, and lexicographic-discrete Helly theorems. We show the relations between these Helly theorems and their corresponding (standard) Helly theorems. We obtain several discrete and lexicographic Helly numbers. Using these types of Helly theorems we get linear time solutions for various optimization problems. For this, we define a framework, DLP-type (discrete linear programming type), and provide algorithms that solve in randomized linear time fixed-dimensional DLP-type problems. We show that the complexity of the DLP-type class stands somewhere between linear programming (LP) and integer programming (IP). Finally, we use our results in order to solve in randomized linear time problems such as the discrete p-center on the real line, the discrete weighted 1-center problem in /spl Ropf//sup d/ with l/sub /spl infin// norm, the standard (continuous) problem of finding a line transversal for a totally separable set of planar convex objects, a discrete version of the problem of finding a line transversal for a set of axis-parallel planar rectangles, and the (planar) lexicographic rectilinear p-center problem for p = 1,2,3. These are the first known linear time algorithms for these problems.