# Tag Info

## Hot answers tagged optimization

11

The problem is very similar to Min Uncut. In Min Uncut, given a graph $G = (V, E)$, we need to find a subset of edges $E'$ s.t. $G - E'$ is bipartite; the objective is to minimize the size of $|E'|$. For brevity, let me call you problem $\cal P$ and Min Uncut $\cal U$. Observation. An instance $G$ of $\cal P$ has a solution of cost 0 if and only if $G$ is ...

4

The following website seems to be no longer maintained, but it is still a useful resource because it covers many problems: http://www.csc.kth.se/~viggo/problemlist/

2

It looks to me like this is a special case of minimum cost flow; introduce one vertex per row and one per column, with an edge for each entry whose cost is the negative of the value of that entry and whose capacity is 1. Then add an edge of capacity $b$ from the source to each row, with cost 0, and similarly for the columns, and solve the resulting minimum ...

2

From a quick Google search, it looks like your problem is sometimes called (metric) "facility dispersion." This paper by Ravi, Rosenkrantz, and Tayi seems to prove that your heuristic is a $2$-approximation, and that this factor is actually optimal by a reduction to clique. I skimmed it, so I might be missing some subtle points, but the idea of the proof ...

2

It seems that the general problem of finding the optimal contraction order is NP-hard [1]. A recent paper on approximately optimizing the contraction order, and containing relevant references, is [2]. [1] Chi-Chung, Lam, P. Sadayappan, and Rephael Wenger. "On optimizing a class of multi-dimensional loops with reduction for parallel execution." ...

1

This may be related to what you have in mind: arxiv.org/abs/0804.4666

1

To simplify life, let $\mathcal V = [n] := \{1,2,\ldots,n\}$. For $A \subseteq [n]$, define $h(A):=\sum_{i \in A}c_i$. Note that $h$ defines a modular (i.e additive) set function. Now, suppose there exists $\gamma \in [0, 1]$ such that $f$ is weakly $\gamma$-submodular, i.e such that  \sum_{i \in B\setminus A}f(A \cup \{i\}) - f(A) \ge \gamma (f(A \cup B)...

Only top voted, non community-wiki answers of a minimum length are eligible