The tag has no wiki summary.

learn more… | top users | synonyms (1)

11
votes
3answers
1k views

Examples of problems where exponential algorithms run faster than polynomial algorithms for practical sizes?

Do you know of any problems (preferably at least somewhat well known), where, for a practical problem size, an exponential algorithm runs much faster than a best-known polynomial time counterpart. ...
0
votes
1answer
178 views

Examples of $2^{\Theta(n^2)}\text{poly}(n)$-time algorithms

What are notable examples of problems for which the best currently known algorithm has $2^{\Theta(n^2)}\text{poly}(n)$ running time ?
3
votes
1answer
75 views

Example of context-free grammar that triggers exponential behaviour without memoization in RD parsers

It is often said that memoization brings the complexity of recursive-descent parsers from exponential to polynomial. However, I had a hard time finding an example grammar that triggers the exponential ...
7
votes
1answer
123 views

$\overline{SAT} \in NTIME(subexp)$?

Is it possible that $\overline{SAT} \in NTIME(\exp(n^{0.9}))$ ? Are there interesting consequences of such containment? Would it contradict the Exponential Time Hypothesis?
2
votes
0answers
371 views

What's the hardest problem with a non-trivial exact algorithm?

Exact algorithms for NP-complete problems are sometimes feasible, if the input is small enough. I’ve also came across some algorithms which are not practical even for very small inputs, and their ...
2
votes
1answer
227 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 ...
9
votes
1answer
249 views

Computational Model in SETH

Impagliazzo, Paturi and Calabro, Impagliazzo, Paturi introduced Exponential-Time Hypothesis (ETH) and Strongly Exponential-Time Hypothesis (SETH). Roughly, SETH says that there is no algorithm which ...
10
votes
2answers
269 views

Hardness of a subcase of Set Cover

How hard is the Set Cover problem if the number of elements is bounded by some function (e.g, $\log n$) where $n$ is the size of the problem instance. Formally, Let $\mathcal{U}=\{e_1, \cdots, ...
16
votes
0answers
418 views

Exact algorithm for NAE-3SAT

The NAE-3SAT problem is to determine whether a given 3CNF formula has a satisfying assignment that gives each clause at least one false (and at least one true) literal. The problem is NP-complete. One ...
8
votes
2answers
344 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 ...
14
votes
0answers
197 views

Exponential-time factorization of polynomials

Let an explicit field be a field for which equality is decidable (in some standard model of computation). I am interested in the factorization of univariate polynomials over an explicit field. It is ...
10
votes
2answers
514 views

Exact exponential-time algorithms for 0-1 programming

Are there known algorithms for the following problem that beat the naive algorithm? Input: A system $Ax \le b$ of $m$ linear inequalities. Output: A feasible solution $x^*\in \{0,1 \}^n$ if ...
3
votes
0answers
175 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}+$ ...
11
votes
1answer
305 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
313 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 ...
18
votes
3answers
836 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? ...
34
votes
4answers
4k 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 ...
3
votes
4answers
1k 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
464 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
181 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). ...
3
votes
3answers
1k 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 ...
9
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 ...
35
votes
1answer
672 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
2k 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 ...