# Questions tagged [exp-time-algorithms]

The tag has no usage guidance.

60 questions
Filter by
Sorted by
Tagged with
13k views

### Approximation algorithms for Metric TSP

It is known that metric TSP can be approximated within $1.5$ and cannot be approximated better than $123\over 122$ in polynomial time. Is anything known about finding approximation solutions in ...
955 views

413 views

373 views

### Subset Numbering

Fix $k\ge5$. For any big enough $n$, we would like to label all subsets of $\{1..n\}$ of size exactly $n/k$ by positive integers from $\{1...T\}$. We would like this labelling to satisfy the following ...
394 views

### Exact exponential-time algorithms for 0-1 programs with nonnegative data

Are there known algorithms for the following problem that beat the naive algorithm? Input: matrix $A$ and vectors $b,c$, where all entries of $A,b,c$ are nonnegative integers. Output: an optimal ...
6k views

### Time complexity of Held-Karp algorithm for TSP

When I looked through "A Dynamic Programming Approach to Sequencing Problems" by Michael Held and Richard M. Karp, I came up with the following question: why the complexity of their algorithm for TSP ...
292 views

### Two DFA intersection emptiness connections to SETH & L vs P

(re "fine grained complexity") Wehar has proved that Two DFA intersection emptiness in $O(n^{2-\epsilon})$ time → SETH false. does anyone see any particular key proof difficulty, challenge, ...
317 views

141 views

### Is it possible to approximate Maximum Independent Set in $O(2^k\text{poly}(n))$ time?

We know that MIS is hard to approximate within a $n^{1-\epsilon}$ factor in polynomial time and that it is $W[1]$-hard and thus unlikely to admit a $f(k)\text{poly}(n)$ time exact algorithm. (here, $k$...
132 views

269 views

### Design of exact algorithms for non-local hard problems

In the connected dominating set problem (CDS) we are given an $n$-vertex undirected graph, and asked to find the smallest connected subset $S$ of vertices such that each vertex not in $S$ is adjacent ...
157 views

### Time complexity of Succinct-CVP

I want to know what is the best known lower time complexity of Succinct-CVP? The succinct version of many P-complete problems are EXP-complete and Succinct-CVP is EXP-complete too (It is because of ...
91 views

Much has been written about the class UP see related (even more in literature) example question here. Much is understood about the class UP, and its place in collapsing the PH too. UP has a played ...
### anything hinting that EXPTIME $\subseteqq$ PSPACE?
Anything or evidence hinting that $$EXPTIME \subseteqq PSPACE$$？