approximation algorithms

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

Strong Formulations and Algorithms for Regularized A-Optimal Design

Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization Tags , , , ,

We study the Regularized A-Optimal Design (RAOD) problem, which selects a subset of \(k\) experiments to minimize the inverse of the Fisher information matrix, regularized with a scaled identity matrix. RAOD has broad applications in Bayesian experimental design, sensor placement, and cold-start recommendation. We prove its NP-hardness via a reduction from the independent set problem. … Read more

Computational Methods for the Household Assignment Problem

Categories Applications - OR and Management Sciences, Approximation Algorithms, Integer Programming Tags , , , ,

We consider the problem of assigning the entries of a household data set to real-world address data. This household assignment problem occurs in the geo-referencing step of spatial microsimulation models. The resulting combinatorial optimization model is a maximum weight matching problem with additional side constraints. Even for real-world instances of medium size, such as the … Read more

A Vectorization Scheme for Nonconvex Set Optimization Problems

Categories Convex and Nonsmooth Optimization, Multi-Criteria Optimization Tags , , , ,

In this paper, we study a solution approach for set optimization problems with respect to the lower set less relation. This approach can serve as a base for numerically solving set optimization problems by using established solvers from multiobjective optimization. Our strategy consists of deriving a parametric family of multiobjective optimization problems whose optimal solution … Read more

On the Value of Multistage Risk-Averse Stochastic Facility Location With or Without Prioritization

Categories Integer Programming, Stochastic Programming Tags , , , , , ,

We consider a multiperiod stochastic capacitated facility location problem under uncertain demand and budget in each period. Using a scenario tree representation of the uncertainties, we formulate a multistage stochastic integer program to dynamically locate facilities in each period and compare it with a two-stage approach that determines the facility locations up front. In the … Read more

Beyond Symmetry: Best Submatrix Selection for the Sparse Truncated SVD

Categories Combinatorial Optimization, Data-Mining, Integer Programming Tags , , , ,

Truncated singular value decomposition (SVD), also known as the best low-rank matrix approximation, has been successfully applied to many domains such as biology, healthcare, and others, where high-dimensional datasets are prevalent. To enhance the interpretability of the truncated SVD, sparse SVD (SSVD) is introduced to select a few rows and columns of the original matrix … Read more

Solving set-valued optimization problems using a multiobjective approach

Categories Multi-Criteria Optimization, Robust Optimization Tags , , ,

Set-valued optimization using the set approach is a research topic of high interest due to its practical relevance and numerous interdependencies to other fields of optimization. However, it is a very difficult task to solve these optimzation problems even for specific cases. In this paper we study set-valued optimization problems and develop a multiobjective optimization … Read more

An approximation algorithm for multi-objective optimization problems using a box-coverage

Categories Global Optimization, Multi-Criteria Optimization Tags , , , ,

For a continuous multi-objective optimization problem, it is usually not a practical approach to compute all its nondominated points because there are infinitely many of them. For this reason, a typical approach is to compute an approximation of the nondominated set. A common technique for this approach is to generate a polyhedron which contains the … Read more

Selective Maximum Coverage and Set Packing

Categories Approximation Algorithms Tags , , , ,

In this paper we introduce the selective maximum coverage and the selective maximum set packing problem and variants of them. Both problems are strongly related to well studied problems such as maximum coverage, set packing, and (bipartite) hypergraph matching. The two problems are given by a collection of subsets of a ground set and index … Read more

Exact and Approximation Algorithms for Sparse PCA

Categories Integer Programming Tags , , , , ,

Sparse Principal Component Analysis (SPCA) is designed to enhance the interpretability of traditional Principal Component Analysis (PCA) by optimally selecting a subset of features that comprise the first principal component. Given the NP-hard nature of SPCA, most current approaches resort to approximate solutions, typically achieved through tractable semidefinite programs (SDPs) or heuristic methods. To solve SPCA to … Read more