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

graph-theory mg.metric-geometry computational-complexity combinatorial-optimization approximation-algorithms

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

answered Aug 9 '20 at 16:50

Carlo Beenakker

130k1212 gold badges318318 silver badges455455 bronze badges

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

#### Related Tags

approximation-algorithms × 136algorithms × 50

graph-theory × 32

co.combinatorics × 25

computational-complexity × 22

na.numerical-analysis × 16

approximation-theory × 12

combinatorial-optimization × 11

linear-algebra × 8

nt.number-theory × 6

real-analysis × 6

linear-programming × 6

pr.probability × 5

matrices × 5

oc.optimization-and-control × 5

convex-polytopes × 4

computer-science × 4

np × 4

reference-request × 3

fa.functional-analysis × 3

mg.metric-geometry × 3

polynomials × 3

sequences-and-series × 3

integration × 3

graph-colorings × 3