Graphs and Matroids

Efficient high-precision dense matrix algebra on parallel architectures for nonlinear discrete optimization

Categories Combinatorial Optimization, Graphs and Matroids, Parallel Algorithms Tags , , , , , , , , , ,

We provide a proof point for the idea that matrix-based algorithms for discrete optimization problems, mainly conceived for proving theoretical efficiency, can be easily and efficiently implemented on massively-parallel architectures by exploiting scalable and efficient parallel implementations of algorithms for ultra high-precision dense linear algebra. We have successfully implemented our algorithm on the Blue Gene/L … Read more

The Rotational Dimension of a Graph

Categories Graphs and Matroids, Semi-definite Programming Tags , , , , ,

Given a connected graph $G=(N,E)$ with node weights $s\in\R^N_+$ and nonnegative edge lengths, we study the following embedding problem related to an eigenvalue optimization problem over the second smallest eigenvalue of the (scaled) Laplacian of $G$: Find $v_i\in\R^{|N|}$, $i\in N$ so that distances between adjacent nodes do not exceed prescribed edge lengths, the weighted barycenter … Read more

The Knapsack Problem with Conflict Graphs

Categories 0-1 Programming, Graphs and Matroids Tags ,

We extend the classical 0-1 knapsack problem by introducing disjunctive constraints for pairs of items which are not allowed to be packed together into the knapsack. These constraints are represented by edges of a conflict graph whose vertices correspond to the items of the knapsack problem. Similar conditions were treated in the literature for bin … Read more

Maximizing Non-monotone Submodular Functions under Matroid and Knapsack Constraints

Categories Approximation Algorithms, Combinatorial Optimization, Graphs and Matroids Tags , , ,

Submodular function maximization is a central problem in combinatorial optimization, generalizing many important problems including Max Cut in directed/undirected graphs and in hypergraphs, certain constraint satisfaction problems, maximum entropy sampling, and maximum facility location problems. Unlike submodular minimization, submodular maximization is NP-hard. In this paper, we give the first constant-factor approximation algorithm for maximizing any … Read more

A Dynamic Programming Framework for Combinatorial Optimization Problems on Graphs with Bounded Pathwidth

Categories Dynamic Programming, Graphs and Matroids, Network Optimization Tags , , , ,

In this paper we present an algorithmic framework for solving a class of combinatorial optimization problems on graphs with bounded pathwidth. The problems are NP-hard in general, but solvable in linear time on this type of graphs. The problems are relevant for assessing network reliability and improving the network’s performance and fault tolerance. The main … Read more

Copositive programming motivated bounds on the stability and the chromatic numbers

Categories Graphs and Matroids, Linear, Cone and Semidefinite Programming Tags , , ,

The Lovász theta number of a graph G can be viewed as a semidefinite programming relaxation of the stability number of G. It has recently been shown that a copositive strengthening of this semidefinite program in fact equals the stability number of G. We introduce a related strengthening of the Lovász theta number toward the … Read more

Hilbert’s Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility

Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Graphs and Matroids Tags , ,

Systems of polynomial equations over an algebraically-closed field K can be used to concisely model many combinatorial problems. In this way, a combinatorial problem is feasible (e.g., a graph is 3-colorable, hamiltonian, etc.) if and only if a related system of polynomial equations has a solution over K. In this paper, we investigate an algorithm … Read more

Polymatroids and Mean-Risk Minimization in Discrete Optimization

Categories (Mixed) Integer Nonlinear Programming, Graphs and Matroids, Integer Programming Tags , , ,

In financial markets high levels of risk are associated with large returns as well as large losses, whereas with lower levels of risk, the potential for either return or loss is small. Therefore, risk management is fundamentally concerned with finding an optimal trade-off between risk and return matching an investor’s risk tolerance. Managing risk is … Read more