# Linked Questions

0answers
39 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 ...
3answers
3k 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 ...
2answers
8k 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, ...
1answer
842 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 ...
2answers
4k 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 ...
1answer
4k 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 ...
1answer
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 ...
1answer
639 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 ...
1answer
3k 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 ...
1answer
295 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 ...
1answer
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 ...
2answers
392 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 ...
3answers
129 views

### How can I evaluate an algorithm for a NP-Hard problem?

I have written a program to calculate the number of stable partition in a graph. ( That is: find which partition of the nodes does not have edges between nodes of the same block. ) The professor, ...
2answers
276 views

### Why does the NP completeness of the Hartree-Fock method not lead to difficulty in practical calculation?

I read Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory. In appendix, it is claimed that In the following, we show that approximating the ...
1answer
733 views

### Searching the best trading route - algorithm

Imagine a village with people trading goods. Each person has his own offer in this format: Giving amount a of good b for amount <...

15 30 50 per page