Skip to main content
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
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

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 …
David Eppstein's user avatar
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 $ …
David Eppstein's user avatar
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 …
David Eppstein's user avatar
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 …
David Eppstein's user avatar
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
David Eppstein's user avatar
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 …
David Eppstein's user avatar
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 …
David Eppstein's user avatar
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 …
David Eppstein's user avatar
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 …
David Eppstein's user avatar
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. …
Community's user avatar
  • 1
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 …
David Eppstein's user avatar
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 …
David Eppstein's user avatar
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 …
David Eppstein's user avatar
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 …
David Eppstein's user avatar
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 …
Community's user avatar
  • 1

15 30 50 per page