# Tag Info

7

No polynomial-time algorithm exists, unless P=NP. Indeed, even for TSP instances where all distances are $1$ or $2$ (note that these automatically satisfy the triangle inequality), Engebretsen and Karpinski showed that it is NP-hard to approximate TSP within a factor of $\frac{741}{740} - \epsilon$, for any $\epsilon > 0$.

4

The question is stated informally, using the terms "queries" and "access". Here is how I formally interpret it: Take any $s$ and $t$ in $(0,1)$. Let $G_{s,t}$ be the set of all continuous strictly increasing functions $g\colon[0,1]\to[0,1]$ such that the set $$E:=E_{s,t}(g):=\{x\in[0,1-s]\colon g(x+s)-g(x)<t\}$$ is nonempty. Do there ...

2

First of all, let us formally interpret the question, as follows: Take any $s$ and $t$ in $(0,1)$. Let $CI_{s,t}$ be the set of all continuous strictly increasing functions $g\colon[0,1]\to[0,1]$. Let $G_{s,t}$ be the set of all functions $g\in CI_{s,t}$ such that the set $$E_{s,t}(g):=\{x\in[0,1-s]\colon g(x+s)-g(x)<t\}$$ is nonempty. Do there exist ...

2

I strongly suspect that this is NP-complete, but the approach I have in mind does not seem to work! I wanted to use the the well-known fact that it is NP-complete to decide whether the chromatic index $\chi'(G)$ of a (simple) cubic graph $G$ is $3$ or $4$ (see this paper of Holyer). For the reduction, start with a simple cubic graph $G$ and double each edge ...

1

You can solve these problems via integer linear programming as follows. Let $c_{i,j}$ be the cost of edge $(i,j)$. Let binary decision variable $x_{i,j,p}$ indicate whether edge $(i,j)$ appears in path $p\in\{1,2\}$. For the min-sum path cost, the problem is to minimize $\sum_{i,j,p} c_{i,j} x_{i,j,p}$ subject to \begin{align} \sum_j x_{i,j,p} - \sum_j x_{...

1

Call $P$ an $\varepsilon$-path if $\max_{t\in[0,T]}w_P(t)\leq\varepsilon$. Define the duration of a path as the maximum $t_e^P$ over all edges $e$ on $P$. For a vertex $u$, let $\tau_\varepsilon(u)$ be the infimum duration over all $\varepsilon$-path from $v_s$ to $u$. Consider the problem of deciding whether an $\varepsilon$-path from $v_s$ to $v_t$ exists; ...

1

Iosif Pinelis proved that, when a solution is guaranteed to exist, it can be found using finitely many queries. When a solution is not guaranteed to exist, then it may be impossible to decide whether or not it exists with finitely many queries. I could prove it for the special case $t = s$. Suppose that, after some $n$ queries, for every $j\in [n]$, the ...

1

On some properties of contracting matrices: For $n_1=n_2$ and if the norm is the $\|\cdots\|_\infty$ norm, then the contractive property (with $\leq$ instead of $<$) is satisfied if the matrix is a Markov matrix (nonnegative real matrix elements with each row summing to 1) and moreover for every pair of rows there exists a column with nonzero entries in ...

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