Skip to main content
Added top-level tag.
Link
Stefan Kohl
  • 19.6k
  • 21
  • 75
  • 137
deleted 1 character in body
Source Link

My questions is concerned with the following problem: Given an undirected graph $G = (V, E)$ and (edge costs) $c \in \mathbb{Z}^E$, $$\min \left\{ \sum_{e \in E} c_e x_e\ \middle|\ x \in \{0,1\}^E \ \wedge\ \forall C \in \mathrm{cycles}(G)\ \forall e \in C:\ x_e \leq \!\!\!\!\sum_{e' \in C \setminus \{e\}} \!\! x_{e'} \right\}$$

This problem, studied by Chopra and Rao (1993), is sometimes called Minimum Cost Multicut, although the term is used also for different problems in the literature (e.g. this problem with terminals and positive edge weights).

Is thisthe problem stated above known to be APX-hard?

My questions is concerned with the following problem: Given an undirected graph $G = (V, E)$ and (edge costs) $c \in \mathbb{Z}^E$, $$\min \left\{ \sum_{e \in E} c_e x_e\ \middle|\ x \in \{0,1\}^E \ \wedge\ \forall C \in \mathrm{cycles}(G)\ \forall e \in C:\ x_e \leq \!\!\!\!\sum_{e' \in C \setminus \{e\}} \!\! x_{e'} \right\}$$

This problem, studied by Chopra and Rao (1993), is sometimes called Minimum Cost Multicut, although the term is used also for different problems in the literature (e.g. this problem with terminals and positive edge weights).

Is this problem stated above known to be APX-hard?

My questions is concerned with the following problem: Given an undirected graph $G = (V, E)$ and (edge costs) $c \in \mathbb{Z}^E$, $$\min \left\{ \sum_{e \in E} c_e x_e\ \middle|\ x \in \{0,1\}^E \ \wedge\ \forall C \in \mathrm{cycles}(G)\ \forall e \in C:\ x_e \leq \!\!\!\!\sum_{e' \in C \setminus \{e\}} \!\! x_{e'} \right\}$$

This problem, studied by Chopra and Rao (1993), is sometimes called Minimum Cost Multicut, although the term is used also for different problems in the literature (e.g. this problem with terminals and positive edge weights).

Is the problem stated above known to be APX-hard?

Source Link

Is it known whether Minimum Cost Multicut is APX-hard?

My questions is concerned with the following problem: Given an undirected graph $G = (V, E)$ and (edge costs) $c \in \mathbb{Z}^E$, $$\min \left\{ \sum_{e \in E} c_e x_e\ \middle|\ x \in \{0,1\}^E \ \wedge\ \forall C \in \mathrm{cycles}(G)\ \forall e \in C:\ x_e \leq \!\!\!\!\sum_{e' \in C \setminus \{e\}} \!\! x_{e'} \right\}$$

This problem, studied by Chopra and Rao (1993), is sometimes called Minimum Cost Multicut, although the term is used also for different problems in the literature (e.g. this problem with terminals and positive edge weights).

Is this problem stated above known to be APX-hard?