The exp-time-algorithms tag has no wiki summary.
2
votes
1answer
85 views
$\mathsf{2EXP} = \mathsf{EXP}^{\mathsf{EXP}}$?
It is clear that any language in $\mathsf{EXP}^{\mathsf{EXP}}$ can be computed in $\mathsf{2EXP} = \mathsf{DTime}(2^{2^{\mathsf{poly}(n)}})$.
My question is whether the converse is true: is ...
3
votes
0answers
100 views
Slightly Faster Exponential Algorithm for Integer Programming with Multi-linear Variables
Integer programing is one of the most narutal optimization tools.
As an analogy of DNF or CNF in the Boolean function theory, we can consider the following equation.
$x_{1}x_{2}x_{3}+$ ...
10
votes
1answer
218 views
Exact algorithms for non-convex quadratic programming
This question is about quadratic programming problems with box constraints (box-QP), i.e., optimisation problems of the form
minimise $f(\mathbf{x}) = \mathbf{x}^T A \mathbf{x} + \mathbf{c}^T ...
10
votes
2answers
276 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 ...
15
votes
3answers
682 views
Solving Superstring Exactly
What is known about exact complexity of the shortest superstring problem? Can it be solved faster than $O^*(2^n)$? Are there known algorithms that solve shortest superstring without reducing to TSP?
...
30
votes
4answers
3k 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 ...
2
votes
4answers
694 views
Finding cliques in a big graph
I would like to find (all) cliques in a given graph with 8,568 vertices and 12,726,708 edges. The vertex with the lowes degree has 2000, the vertext with the highest degree has 4007.
The cliques ...
1
vote
1answer
368 views
Learning about EXPTIME and EXPSPACE
I'd like to know some good starting points (such as books, papers, lecture notes, etc.) on EXPTIME and EXPSPACE. I'd like to learn more about these two topics, but I'm not sure what the best approach ...
1
vote
0answers
162 views
Upper bound for set cover with respect to m that is better than trivial when $n \ge 3m$
Does anyone know of an upper bound for Set Cover $(\mathcal{U}, \mathcal{S}, k)$ with respect to $m=|\mathcal{S}|$ that is better than trivial when $n =|\mathcal{U}|$ is at least $3m$?
(Set cover).
...
-1
votes
1answer
124 views
Better solution to sort with modified cost [closed]
First, this was one of the four problems we had to solve last year and we couldn’t find a suitable algorithm so we handle in a brute force solution, the problem is that our tutor said he couldn’t find ...
3
votes
3answers
854 views
Pseudo-polynomial time algorithms
Consider the following algorithm:
Given a natural number as input, say $N$, the algorithm runs a loop (in which the algorithm does $O(1)$ time operations) $N$ times. Now, by definition of time ...
8
votes
1answer
3k 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 ...
33
votes
1answer
609 views
How many distinct colors are needed to lower-bound the choosability of a graph?
A graph is $k$-choosable (also known as $k$-list-colorable) if, for every function $f$ that maps vertices to sets of $k$ colors, there is a color assignment $c$ such that, for all vertices $v$, ...
0
votes
2answers
1k views
Dynamic programming algorithm for NP-complete problem
Hello everybody here is a problem i have approximated but would like to hear your opinion about. Perhaps someone finds a better solution than me :)
Given a Graph G with undirected edges:
Divide it ...
