Questions tagged [application-of-theory]

Questions arising from applications of theoretical computer science in other areas of computer science research/practice or other subjects.

Filter by
Sorted by
Tagged with
4
votes
1answer
157 views

Given a network flow, are there bounds on the change in weight on nodes?

Here's my precise situation: I have a graph with nodes $V$ and edges $E$, and the nodes have some non-negative integer weights $w_i$. In one step of the protocol, I am now allowed to move weight ...
7
votes
2answers
297 views

Is there a local variant of TSP?

I'm a traveling salesman and I have n days to sell, I can start anywhere, I can sell once per city. I want to know where to start and what route to take. It's likely NP-hard, I was just wondering if ...
6
votes
1answer
414 views

Physics and TCS

I was curious as to the ability to move between different academic disciplines with an advanced degree in TCS. So would I be able to move, with a little bit of elbow grease, between physics and ...
2
votes
2answers
774 views

Suggestions on a matching/scheduling algorithm.

I have a problem where mentors need to paired with courses, this is similar to the marriage problem or the hospitals/residents problem except that it isn't. The current solution is terribly written ...
12
votes
1answer
915 views

NP-hardness of a special case of Number Partitioning

Consider the following problem, Given a set of $n = k m$ positive numbers $\{ a_1, \dots, a_n \}$ in which $k \ge 3$ is a constant, we want to partition the set into $m$ subsets of size $k$ so that ...
12
votes
2answers
443 views

Euclidean-squared max-cut in low dimensions

Let $x_1, \ldots, x_n$ be points in the plane $\mathbb{R}^2$. Consider a complete graph with the points as vertices and with edge weights of $\|x_i - x_j\|^2$. Can you always find a cut of weight that ...
10
votes
1answer
3k views

Minimum path covering problem

We are working in distributed computers, and we came up with a complexity problem which reduces to a minimum path covering problem. We currently do not know how to solve it. The problem is the ...
15
votes
3answers
506 views

Bob's Sale (reordering of pairs with constraints to minimize sum of products)

I've asked this question on Stack Overflow a while ago: Problem: Bob's sale. Someone suggested posting the question here as well. Someone has already asked a question related to this problem here - ...
11
votes
6answers
20k views

Application of graph theory in computer science

I am a CS student. We did graph theory in one course. I found it interesting. What are the real applications of graph theory in the computer science field? For example, I found that some concepts ...
11
votes
1answer
279 views

Minimum weight subforest of given cardinality

This question was motivated by a question asked on stackoverflow. Suppose you are given a rooted tree $T$ (i.e. there is a root and nodes have children etc) on $n$ nodes (labelled $1, 2, \dots, n$). ...
7
votes
2answers
2k views

Applications of computer science in biology

Is there a survey or tutorial article which talks about application of theoretical computer science to emerging fields of applications of computer science in biology, bioinformatics and nanotechnology?...
6
votes
2answers
278 views

Practical applications of the Theory of Equality with Uninterpreted Functions (EUF)

In these days I'm reading the book Decision Procedures - An Algorithmic Point of View. Chapters 3 and 4 deal with the Theory of Equality with Uninterpreted Functions (EUF). The authors give 3 toy ...
20
votes
4answers
611 views

Is there current research into the implemention of Randomness Extractors?

Has there been research into implementing randomness extractor constructions? It seems that extractor proofs make use of Big-Oh, leaving the possibility for large hidden constants, making ...
8
votes
1answer
620 views

Is that particular case of the “minimum weight solution to linear equations” still NP-complete?

We in our research group are working in the application of heuristic methods to the inverse illumination problem (that is, given a set of constraints about the illumination conditions in a scene, find ...
4
votes
3answers
472 views

Is Degrees Of Separation NP Complete?

I'm doing a bit of research on doing social analysis between so called "hub" people. Basically what I want to try to do is determine the shortest paths between two individuals. The problem is that ...
12
votes
3answers
3k views

What are some examples of secret sharing schemes actually being used in real-world applications?

The concept of a secret sharing scheme is often attributed to Shamir (A. Shamir, How to share a secret, Comm. ACM, 22 (1979), pp. 612-613.) and Blakey (G. R. Blakey, Safeguarding cryptographic keys, ...
13
votes
12answers
5k views

What are some real world applications for genetic algorithms?

What are some real world problems that have been solved using a genetic algorithm? What is the problem? What is the fitness test used to solve this problem?