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 |
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
Enumerating the elements of cartesian products in ascending order of $\|\cdot\|_1$ norm
Even the case $n=2$ is a well-known open problem, X + Y sorting. It is unknown whether one can list the elements faster than the time it would take to apply a general-purpose sorting algorithm.
If you …
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 $ …
3
votes
Algorithm for reporting all triangles with unique interior point
Given any two points $p$ and $q$, consider the points above line $pq$. You want to list all points $r$ such that $pqr$ contains exactly one additional point.
To do so, sort the points radially around …
3
votes
Accepted
Calculating radii allowing for circular placement of polygonal linkage's joints
This problem has an algebraic-number solution (set up a system of quadratic equalities between the squared link lengths and the squared distances between hinge points) but with unsolvable Galois group …
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 …
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 …
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 …
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 …
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 …
31
votes
Algorithm for finding the volume of a convex polytope
Simonovits, Random walks and an O*(n^5) volume algorithm for convex bodies, Random structures and algorithms, 1997. …
6
votes
Is this problem on weighted bipartite graph solvable in polynomial time or it is NP-Complete
It's NP-complete (even for 0-1 weights) by a reduction from feedback arc set in directed graphs. Let D be a digraph in which you want to compute a feedback arc set, A be the vertices of D, B be the ed …
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 …
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 …
2
votes
Accepted
Finding a vertex of least distance to all other vertices in a graph
A graph as you describe is normally called a tree, and yes, it is easy to compute the sum of distances to all other vertices in a tree.
First, choose one of the leaves (arbitrarily) to be the root of …
12
votes
Determine if circle is covered by some set of other circles
See this earlier MO question. The union of n disks (represented in terms of its boundary arcs) can be constructed in $O(n\log n)$ time. So construct the union of the $n$ disks you are given, and separ …