Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with algorithms
Search options answers only
not deleted
user 440
Informally, an algorithm is a set of explicit instructions used to solve a problem (e.g. Euclid's algorithm for computing the greatest common divisor of two integers). For more specific questions on algorithms, this tag may be used in conjunction with the approximation-algorithms, algorithmic-randomness and algorithmic-topology tags.
1
vote
Water jug puzzle
See "Matching nuts and bolts" by Alon et al from SODA 1994, on exactly this problem.
- 18.6k
6
votes
Accepted
$k$-th subset in order of increasing sum
Since this is MathOverflow I'll give you the mathematical answer rather than the practical answer. I'll assume all numbers are positive; otherwise minor modifications would be needed to handle negativ …
- 18.6k
1
vote
Accepted
Algorithms for Sorting Subset Sums
One standard situation where sorted subset sums comes up is in the subset sum problem. (I.e. is zero among the subset sums of a given set?) By splitting the input into two equinumerous subsets, sortin …
- 18.6k
3
votes
How to prove that the A* Algorithm is admissible (by induction)?
Your question is a little confusing: it's the heuristic estimate of distance to the destination that's supposed to be admissable in A*, not the algorithm itself. I assume what you actually mean is: su …
- 18.6k
2
votes
Accepted
Algorithm for finding mesh subgraphs?
So, yes, there are algorithms — you can just do a brute force search over all permutations of the vertices, for instance — but not polynomial algorithms. …
- 18.6k
3
votes
What is the most general class of metric spaces for which the closest pair of points in a fi...
A popular assumption in theoretical computer science for algorithms of this type is that the metric have bounded "doubling dimension". … For randomized near-linear closest pair algorithms with this assumption, see e.g. Hildrun, Kubiatowicz, Ma, and Rao, "A note on the nearest neighbor in growth-restricted metrics", SODA 2004. …
- 18.6k
9
votes
Accepted
Good algorithm for finding the diameter of a (sparse) graph?
helpful in the dense case, not the sparse case that you're asking about, but Yuster has recently shown that the diameter of an unweighted directed graph can in fact be computed more efficiently than known algorithms …
- 18.6k
11
votes
Accepted
Algorithm to find all the cycle bases in a graph
Maybe what you want is a cycle basis? That is, a set of cycles such that any other cycle can be found by adding and subtracting combinations of cycles in the basis. One can find a cycle basis easily f …
- 18.6k
5
votes
Sub-linear algorithm for minimum spanning tree (MST) for a tree metric.
Let $T$ be a star with weights 1, 2, 3, 4, ... on its edges. Then unless you test the distance between every two leaves of $T$ you can't distinguish it from a different tree where some two leaves whos …
- 18.6k
1
vote
Accepted
Finding Optimal Vertex Weights without Linear Programing
It is the dual of the LP relaxation of a weighted matching problem, and (even though the relaxation allows fractional solutions instead of just 0-1 solutions) it can be solved by graph matching based algorithms …
- 18.6k
11
votes
Optimization algorithm sought
It is equivalent to look for the largest positive value $x$ such that, for some $M$-subset, $\sum (a_i-x b_i)\ge 0$.
Plot the $n$ lines $y = a_i - x b_i$ in the plane. The $M$-subset that maximizes $ …
- 18.6k
16
votes
Accepted
duplicate detection problem
It also contains a proof that an algorithm that makes only a single pass over the data cannot solve the problem exactly and deterministically, but of course that doesn't apply to algorithms with random …
- 18.6k
3
votes
Accepted
Finding integer representation as difference of two triangular numbers
The representations of this type correspond one-for-one to odd divisors of $n$. So your request for a method for constructing such a representation without factoring seems to be hopeless: if you have …
- 18.6k
1
vote
Relaxed path decomposition of a graph
No, because your assumptions are not strong enough to ensure that all edges belong to final paths. For instance, if the graph has any edges into $v$ itself, then these edges cannot belong to final pat …
- 18.6k
3
votes
Counting simple 4-cycles in an undirected graph
In an undirected graph with $m$ edges there can be as many as $\Theta(m^2)$ simple 4-cycles, so that's a reasonable time bound to aim for. And it's easy enough to achieve: set up a data structure that …
- 18.6k