Linked Questions

1 vote
0 answers
44 views

Minimum vertices to cover other vertices with max weight [duplicate]

I have a problem where I'm given the input of a graph. The output would be a set of vertices such that I have the minimum number of vertices to cover other vertices and if there is more than one ...
RandomGuy's user avatar
  • 111
10 votes
9 answers
6k views

Why is proving something is NP-complete useful, and where can I use it?

I trying to understand where, as a programmer in situations where it can be good to do a NP-complete reduction to prove that a problem is NP-complete, why is it good to do that as a programmer? I don'...
Jonte YH's user avatar
  • 443
19 votes
3 answers
4k views

Why there are no approximation algorithms for SAT and other decision problems?

I have an NP-complete decision problem. Given an instance of the problem, I would like to design an algorithm that outputs YES, if the problem is feasible, and, NO, otherwise. (Of course, if the ...
Ribz's user avatar
  • 693
10 votes
2 answers
13k views

What is practical difference between NP and PSPACE-complete?

Here's something that has puzzled me lately, and perhaps someone can explain what I'm missing. Problems in NP are those that can be solved on a NDTM in polynomial time. Now assuming P$\,\neq\,$NP, ...
Motorhead's user avatar
  • 282
4 votes
4 answers
6k views

Is there any NP-hard problem which was proven to be solved in polynomial time or at least close to polynomial time?

I know this could be a strange question. But was there any algorithm ever found to compute an NP-problem, whether it be hard or complete, in polynomial time. I know this dabbles into the "does P=...
MathIsFun's user avatar
3 votes
2 answers
5k views

Algorithm for finding maximum mutually coprime subset of a multiset of integers

For a certain problem I am trying to solve given a list of integers, it is advantageous to me to first identify as many of the integers that are mutually coprime as possible. I'm having trouble ...
user3030010's user avatar
6 votes
1 answer
905 views

$1+\epsilon$ approximation for inapproximable problems

I am currently confused by the following situation: 1) The metric $k$-center problem is inapproximable in polynomial time within $2-\epsilon$ unless $P=NP$. 2) The metric $k$-center problem can ...
jack's user avatar
  • 63
8 votes
1 answer
5k views

Weighted interval scheduling with m-machines

I am looking for some advice and direction on solving the weighted interval scheduling problem with $m$-machines to plan some experimental "wet lab" procedures. The problem is very similar to the ...
tomnl's user avatar
  • 81
3 votes
1 answer
4k views

Longest path in a cyclic, directed and weighted graph

I am looking for the longest simple path in a directed, cyclic and weighted graph with positive and negative weights. In my research so far I have found out that you need to generate ...
Bobface's user avatar
  • 321
7 votes
1 answer
2k views

NP complete problems that are solvable in polynomial time if the input (e.g. number of variables) is fixed?

I have seen some problems that are NP-hard but polynomially solvable in fixed dimension. Examples, I think, are Knapsack that is polynomial time solvable if the number of items is fixed and Integer ...
user2145167's user avatar
5 votes
1 answer
807 views

NP-complete decision problems - how close can we come to a solution?

After we prove that a certain optimization problem is NP-hard, the natural next step is to look for a polynomial algorithm that comes close to the optimal solution - preferrably with a constant ...
Erel Segal-Halevi's user avatar
14 votes
1 answer
340 views

How can you bound the error of an approximation without knowing the optimal solution?

I been looking at this site and it says that people found solutions for TSP tours that are just 0.031% higher than the optimal tour is. Without finding the optimal tour how does they know what length ...
Ilya Gazman's user avatar
4 votes
1 answer
1k views

Cover points with minimal number of spheres of fixed radius

I have a set of k n-dimensional points: P1(x11, x12, ..., x1n), P2(x21, x22, ..., x2n), ..., Pk(xk1, xk2, ..., xkn). A distance D(Pa, Pb) is defined between any two points, which satisfy usual ...
user avatar
2 votes
1 answer
820 views

How to find subset of vectors whose sum has certain characteristics

Let's say you have list of $n$ vectors with entries from $\{0,1,x\}$ and $x$ is > $n$: $$ \begin{align*} L_0 &= [1,0,x] \\ L_1 &= [1,1,1] \\ L_2 &= [1,0,0] \\ L_3 &= [x,1,0] \\ L_4 &...
Akim Akimov's user avatar
4 votes
2 answers
484 views

Pick a subgraph that maximizes the total cost of min-spanning tree among all subgraphs of the same size

There is a complete graph $G$ with $n$ vertices and each edge has a distinct weight. Is there an efficient (not necessarily optimal) algorithm to select $k$ vertices from the graph $G$, such that the ...
Blaz Bratanic's user avatar

15 30 50 per page