All Questions
8 questions
7
votes
1
answer
171
views
Metric TSP with integer edge cost
Given a metric TSP with integer edge cost upper-bounded by a constant $C_{\max}$, can we find an poly-time algorithm solving this TSP instance?
- 367
2
votes
1
answer
112
views
Finding survivable paths with a set of vulnerable edges
Consider a graph $G=(V,E)$ and a source-destination pair $(s,t)$. A set of edges $E'\subseteq E$ are vulnerable in the sense that at most $k$ of them may fail. My problem is to find a set of $(s,t)$ ...
- 367
2
votes
0
answers
63
views
Maximize connectivity probability with a number of edges
We are given a graph $G$, whose edges are either open or closed. Initially all the edges are closed. For each edge $e$, if we choose to activate it, then after the activation, it becomes open with ...
- 367
1
vote
0
answers
65
views
Find a cut of a graph that minimizes the ratio between the edge weights of the cut and the edge weights inside one subgraph
Given an edge-weighted undirected graph $G=(V,E)$ (can assume the weights are non-negative) and a source node $v_s\in V$, a cut is a partition of $G$'s vertices into two complementary sets $S$ and $T$....
- 143
0
votes
0
answers
24
views
Minimizing intersections between spanning trees of graph embeddings in polynomial time
Assume I have $N$ complete graphs $G_1, G_2,...,G_N$, and consider their embeddings $E_1, E_2,...,E_N$ in $\mathbb{R}^2$. Is there a (potentially stochastic) polynomial time algorithm to construct ...
- 1
0
votes
0
answers
123
views
A variant of Steiner tree
Consider a directed Steiner tree problem with a source node $s$ a set $T$ of terminals with the following constraint. For each node $v$ on the tree, we assign a branching value $b_v$ as follows. (1) $...
- 367
0
votes
0
answers
50
views
Can we talk about approximation when the decision problem for solution existence is NP-Hard
I am wishing to design an approximation algorithm for an optimization problem where the existence of solution for corresponding decision problem is not guaranteed. Is it wise to find an approximation ...
0
votes
0
answers
36
views
Approximabilty of submodular over modular maximization
Given a non-decreasing, normalized, submodular function $f : 2^{[n]}\mapsto \mathbb{R}_+$ and a modular non-decreasing function $g$, I am wondering what is the best approximation ratio I can hope for ...
- 171