Approximation Algorithms

A Generalized Polynomial Lower Bound for the Weighted Completion Time Variance in a Single Machine

Categories Approximation Algorithms, Combinatorial Optimization, Scheduling Tags , , ,

This paper studies the single-machine problem of minimizing the weighted completion time variance (WCTV) and proposes a polynomially computable lower-bounding framework that generalizes the benchmark introduced by Nessah and Chu (2010). We first develop a generalized augmented-sequence decomposition that mathematically connects the weighted problem with the classical unweighted variance setting. Using this decomposition, we derive … Read more

A tight 1/3–approximation algorithm and fully polynomial-time approximation schemes for the Colored Knapsack Problem

Categories Approximation Algorithms, Combinatorial Optimization, Dynamic Programming Tags , , ,

The \(\textit{Colored Knapsack Problem}\) (ColKP) generalizes the classical Knapsack Problem by partitioning the items into color classes and requiring the selected items to admit an ordering in which consecutive items have different colors. The problem is weakly \(\mathcal{NP}\)-hard and admits two pseudo-polynomial dynamic programming (DP) algorithms proposed in the literature. These two DP algorithms have … Read more

Maximum Cuts and Fractional Cut Covers: A Computational Study of a Randomized Semidefinite Programming Approach

Categories Approximation Algorithms, Optimization Software and Modeling Systems, Semi-definite Programming

We present experimental work on a primal-dual framework simultaneously approximating maximum cut and weighted fractional cut-covering instances. In this primal-dual framework, we solve a semidefinite programming (SDP) relaxation to either the maximum cut problem or to the weighted fractional cut-covering problem, and then independently sample a collection of cuts via the random-hyperplane technique. We then … Read more

A Structural Equivalence of Symmetric TSP to a Constrained Group Steiner Tree Problem

Categories (Mixed) Integer Linear Programming, Approximation Algorithms Tags , , , ,

We present a brief structural equivalence between the symmetric TSP and a constrained Group Steiner Tree Problem (cGSTP) defined on a simplicial incidence graph. Given the complete weighted graph on the city set V, we form the bipartite incidence graph between triangles and edges. Selecting an admissible, disk-like set of triangles induces a unique boundary … Read more

A Tight 2-Approximation Algorithm for the Bin Packing Problem with Setups

Categories Approximation Algorithms, Combinatorial Optimization

We study approximation algorithms for the Bin Packing Problem with Setups (BPPS), a generalization of the classical Bin Packing Problem (BPP) in which items are partitioned into classes and activating a class in a bin consumes a setup weight and incurs a setup cost. We show that direct adaptations of Next Fit (NF), First Fit … Read more

Greedy Algorithms with Imprecise Oracles for Submodular Knapsack Problems

Categories Approximation Algorithms, Combinatorial Optimization Tags , , ,

We consider the problem of maximizing a monotone increasing, normalized, and submodular function defined on a set of weighted items under a knapsack constraint. A well-known greedy algorithm, analyzed by Wolsey (1982), achieves an approximation factor of \(0.357\) for this problem. This greedy algorithm starts with an empty solution set and iteratively generates a feasible … Read more

Recoverable Robust Cardinality Constrained Maximization with Commitment of a Submodular Function

Categories Approximation Algorithms, Combinatorial Optimization Tags , , ,

We consider a game-theoretic variant of maximizing a monotone increasing, submodular function under a cardinality constraint. Initially, a solution to this classical problem is determined. Subsequently, a predetermined number of elements from the ground set, not necessarily contained in the initial solution, are deleted, potentially reducing the solution’s cardinality. If any deleted elements were part … Read more

Novel closed-loop controllers for fractional linear quadratic tracking systems

Categories Applications - Science and Engineering, Approximation Algorithms, Systems governed by Differential Equations Optimization Tags , , , , ,

A new method for finding closed-loop optimal controllers of fractional tracking quadratic optimal control problems is introduced. The optimality conditions for the fractional optimal control problem are obtained. Illustrative examples are presented to show the applicability and capabilities of the method. ArticleDownload View PDF

Two approaches to piecewise affine approximation

Categories Applications - OR and Management Sciences, Approximation Algorithms, Data-Mining Tags , , ,

The problem of approximation by piecewise affine functions has been studied for several decades (least squares and uniform approximation). If the location of switches from one affine piece to another (knots for univariate approximation) is known the problem is convex and there are several approaches to solve this problem. If the location of such switches … Read more

Sequential Rounding in Mixed-Integer Model Predictive Control

Categories Approximation Algorithms, Control Applications, Systems governed by Differential Equations Optimization Tags , , ,

This paper interfaces combinatorial integral approximation strategies with the inherent robustness properties of conventional model predictive control with stabilizing terminal conditions to establish practical asymptotic stability results for finite control set and mixed-integer model predictive control. We examine the impact of sequential control rounding on the closed-loop performance in terms of stability and optimality. Sum-up … Read more