Improved dynamic programming and approximation results for the knapsack problem with setups

We consider the 0-1 Knapsack Problem with Setups (KPS). Items are grouped into families and if any items of a family are packed, this induces a setup cost as well as a setup resource consumption. We introduce a new dynamic programming algorithm which performs much better than a previous dynamic program and turns out to … Read more

A 2-approximation algorithm for the minimum knapsack problem with a forcing graph

Carnes and Shmoys (2015) presented a 2-approximation algorithm for the minimum knapsack problem. We extend their algorithm to the minimum knapsack problem with a forcing graph (MKPFG), which has a forcing constraint for each edge in the graph. The forcing constraint means that at least one item (vertex) of the edge must be packed in … Read more

Approximation Properties and Tight Bounds for Constrained Mixed-Integer Optimal Control

We extend recent work on mixed-integer nonlinear optimal control prob- lems (MIOCPs) to the case of integer control functions subject to constraints. Promi- nent examples of such systems include problems with restrictions on the number of switches permitted, or problems that minimize switch cost. We extend a theorem due to [Sager et al., Math. Prog. … Read more

Exploiting Optimization for Local Graph Clustering

Local graph clustering methods aim to identify well-connected clusters around a given “seed set” of reference nodes. The main focus of prior theoretical work has been on worst-case running time properties or on implicit statistical regularization; and the focus of prior empirical work has been to identify structure in large social and information networks. Here, … Read more

Optimization over Structured Subsets of Positive Semidefinite Matrices via Column Generation

We develop algorithms for inner approximating the cone of positive semidefinite matrices via linear programming and second order cone programming. Starting with an initial linear algebraic approximation suggested recently by Ahmadi and Majumdar, we describe an iterative process through which our approximation is improved at every step. This is done using ideas from column generation … Read more

A Deterministic Fully Polynomial Time Approximation Scheme For Counting Integer Knapsack Solutions Made Easy

Given $n$ elements with nonnegative integer weights $w=(w_1,\ldots,w_n)$, an integer capacity $C$ and positive integer ranges $u=(u_1,\ldots,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 … Read more

Sum of Squares Basis Pursuit with Linear and Second Order Cone Programming

We devise a scheme for solving an iterative sequence of linear programs (LPs) or second order cone programs (SOCPs) to approximate the optimal value of any semidefinite program (SDP) or sum of squares (SOS) program. The first LP and SOCP-based bounds in the sequence come from the recent work of Ahmadi and Majumdar on diagonally … Read more

Semi-Online Scheduling on Two Uniform Machines with Known Optimum, Part I: Tight Lower Bounds

This problem is about to schedule a number of jobs of different lengths on two uniform machines with given speeds $1$ and $s \geq 1$, so that the overall completion time, i.e., the makespan, is earliest possible. We consider a semi-online variant (introduced for equal speeds) by Azar and Regev, where the jobs arrive one … Read more

Semi-Online Scheduling on Two Uniform Machines with Known Optimum, Part II: Tight Upper Bounds

We consider a semi-online version of the problem of scheduling a sequence of jobs of different lengths on two uniform machines with given speeds $1$ and $s$. Jobs are revealed one by one (the assignment of a job has to be done before the next job is revealed), and the objective is to minimize the … Read more

Fully Polynomial Time hBcApproximation Schemes for Continuous Stochastic Convex Dynamic Programs

We develop fully polynomial time $(\Sigma,\Pi)$-approximation schemes for stochastic dynamic programs with continuous state and action spaces, when the single-period cost functions are convex Lipschitz-continuous functions that are accessed via value oracle calls. That is, for every given additive error parameter $\Sigma>0$ and multiplicative error factor $\Pi=1+\epsilon>1$, the scheme returns a feasible solution whose value … Read more