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 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." ...


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

The statement of the problem is incorrect. But $T$-joins are indeed very much related to the perfect matching problem. What the theorem that 9.3a is supposed to be conveying is: Assume $G$ is connected. Suppose that $T = V$. The minimum $T$-join can be found as follows: construct a complete graph $G'$ such that the weight on an edge (a,b) in $G'$ is the ...


1

As far as I have understood, you aim to develop a framework to capture the hardness of combinatorial problems in 3D. However, there are major problems in your question. Your first sentence lacks a couple of technical definitions: For a specific f(), I'm defining a term 'complexity', estimating how difficult is the given function to optimize. First, and the ...


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