Questions tagged [algorithms]
An algorithm is a sequence of well-defined steps that defines an abstract solution to a problem. Use this tag when your issue is related to design and analysis of algorithms.
2,697
questions with no upvoted or accepted answers
37
votes
0
answers
632
views
Finding an $st$-path in a planar graph which is adjacent to the fewest number of faces
I am curious whether the following problems has been studied before, but wasn't able to find any papers about it:
Given a planar graph $G$, and two vertices $s$ and $t$, find an
$s$-$t$ path $P$ ...
- 371
30
votes
0
answers
740
views
Largest set of cocircular points
Given $n$ points with integer coordinates in the plane, determine the maximum number of points that lie on the same circle (on its circumference, not its interior).
This can be done in $O(n^3)$ ...
- 421
24
votes
1
answer
1k
views
Compression of domain names
I am curious as to how one might very compactly compress the domain of an arbitrary IDN hostname (as defined by RFC5890) and suspect this could become an interesting challenge. A Unicode host or ...
- 349
19
votes
0
answers
463
views
Is finding a weight-balanced tree NP-hard?
In the following, we consider binary trees where only the leaves have weights.
Let $T$ be a binary tree and $W(T)$ be the sum of the weights of its leaves.
Let $T.l$ and $T.r$ be the left child and ...
- 316
16
votes
2
answers
765
views
Steps that guarantee exiting a maze
Given a 2-dimensional maze where you can give 4 commands "move up/down/right/left". Knowing the maze but not where the person is, how to find the minimum sequence of commands that guarantees exiting ...
- 261
14
votes
0
answers
684
views
Test whether two languages are equal, when give in algebraic form
This sub-problem is motivated by Algorithm to test whether a language is regular.
Suppose we have two languages $L_1,L_2$ that are expressed in "algebraic" form, as formalized below. I want to ...
D.W.♦
- 152k
13
votes
0
answers
425
views
Choosing a subset of binary variables to maximize the sum of the highest $K$
Consider the following problem:
Input:
integers $n > m > k$;
$n$ numbers $0 \leq p_1, \ldots, p_n \leq 1$;
$n$ numbers $r_1, \ldots, r_n$ where ($r_i \geq 0$).
Let $X_1,\dots,X_n$ be $n$ ...
- 231
12
votes
0
answers
881
views
Optimal meeting point in directed graph
Let $G(V, E)$ be a edge-weighted directed connected graph and $v_1, \dots, v_n \in V$ be some vertices. Let $d(a, b)$ denote the length of the shortest path from $a$ to $b$, for $a,b \in V$.
I need ...
- 221
12
votes
0
answers
804
views
Fast algorithm for max-convolution with concave functions?
I'm interested in a discrete max-convolution problem, which is to compute
$$r(c) = \max_{x | x \ge 0, \sum_k x_k = c} \left[ \sum_{k=1} f_k(x_k) \right] $$
for all values $c=0, \ldots, C$, where $x=(...
- 221
11
votes
0
answers
221
views
Covering a complete graph with n copies of an arbitrary graph: NP-complete?
Given a complete graph $G$, an arbitrary graph $H$, and a positive
integer $n$, are there subgraphs $A_1,\dots,A_n$ of $G$ (not necessarily disjoint) such that
their union is $G$, and each of them ...
11
votes
0
answers
202
views
Can you multiply complex 2x2 matrices in fewer than 21 real multiplies?
It is well known that 2x2 matrices can be multiplied using just 7 (instead of the obvious 8) multiplications in the ground field (Strassen-Winograd, etc.). It is also well known that complex numbers ...
- 191
11
votes
0
answers
366
views
Change in the distances in a graph after removal of a node
Given an undirected unweighted graph $G=(V,E)$ and a node $s \in V$, we are looking for a vector $\operatorname{diff}[]$, such that,
$$\operatorname{diff}[v] = \sum_{u \in V \setminus \{v\}}{(d^{G \...
- 1,934
11
votes
0
answers
2k
views
Alternatives to SVD for rank factorization
I have rank-deficient matrix $M \in \mathbb{R}^{n\times m}$ with $\text{rank}(M) = k$ and I want to find a rank factorization $M = PQ$ with $P \in \mathbb{R}^{n \times k}$ and $Q \in \mathbb{R}^{k \...
- 4,792
11
votes
1
answer
4k
views
Finding the longest repeating subsequence
Given a string $s$, I would like to find the longest repeating (at least twice) subsequence. That is, I would like to find a string $w$ which is a subsequence (doesn't have to be a contiguous) of $s$ ...
- 494
10
votes
1
answer
437
views
Shift-resolve parsing - questions
I've recently came across a paper describing the parsing technique
mentioned in the title. Unfortunately, the terminology used in said paper
is somewhat beyond my comprehension, so I've been ...
- 233
9
votes
1
answer
1k
views
Why is the complexity of negative-cycle-cancelling $O(V^2AUW)$?
We want to solve a minimal-cost-flow problem with a generic negative-cycle cancelling algorithm. That is, we start with a random valid flow, and then we do not pick any "good" negative cycles such as ...
- 261
8
votes
0
answers
410
views
Shortest path that can be split into contiguous segments of 5 edges connecting 6 distinct nodes in an unweighted graph
The following problem (I'm paraphrasing) appeared in the 2019 Balkan Olympiad in Informatics:
Five friends are on a road trip in a country with $N$ cities and $M$ bidirectional roads joining them. ...
- 121
8
votes
2
answers
449
views
NP-hardness for one-dimensional facility location problem with entrance fee for each customer
We have $n$ customers, $(x_1, \dots, x_n)$, sorted on the read line. For convenience, we also use $x_i$ to denote its coordinate on the line. We need to locate $m$ facilities on the real line. We note ...
- 61
8
votes
1
answer
274
views
Polynomial time algorithm for finding a maximal monotone subset
Input:
Some fixed $k>1$, vectors $x_i,y_i\in\mathbb R^k$ for $1\le i\le n$.
Output:
A subset $I\subset\{1,\dots,n\}$ of maximal size such that
$(x_i-x_j)^T(y_i-y_j) \ge 0$ for all $i,j\in I$.
...
- 131
8
votes
0
answers
230
views
What is the best algorithm to compute ALL homomorphisms between two rooted labeled trees?
Lets consider two node-labeled rooted trees Q and D.
According to wikipedia definition ( https://en.wikipedia.org/wiki/Tree_homomorphism ) a mapping m from the nodes of Q to the nodes of D is a tree ...
- 343
8
votes
0
answers
234
views
Practical algorithms for the disjoint paths problem
Given an undirected graph $G$ and two pairs of vertices $(s_1, t_1), (s_2, t_2)$, the disjoint paths problem (DPP) asks for two vertex-disjoint paths, one from $s_1$ to $t_1$ and the other from $...
- 81
8
votes
0
answers
989
views
Find set of points with maximum distance inside given intervals?
Let $A$ be a set of $n$ closed intervals, $I_i$, with both extremes positive integers. Is there an efficient algorithm to find a set of $n$ points $P_i$, with $P_i \in I_i$, such that the minimum ...
- 209
8
votes
0
answers
2k
views
Area of the union of rectangles anchored on the x-axis
I am trying to solve the following computational geometry problem.
Let $S$ be a set of $n$ axis-parallel rectangles in the plane, so that the bottom edge of each rectangle in $S$ lies on the $x$-axis....
- 3,139
8
votes
0
answers
1k
views
Weighted Maximum 3-DIMENSIONAL-MATCHING with restricted weights (Approx Algo)
If the weights of the weighted 3-DIMENSIONAL-MATCHING problem are restricted to let's say, 1 and 2, is there a possibility to reduce this case to the unweighted 3-DIMENSIONAL-MATCHING problem?
(...
- 81
8
votes
0
answers
207
views
Optimizing order of graph reduction to minimize memory usage
Having extracted the data-flow in some rather large programs as directed, acyclic graphs, I'd now like to optimize the order of evaluation to minimze the maximum amount of memory used.
That is, given ...
- 81
8
votes
1
answer
143
views
Find all the special graphs which can reduced to the shortest paths graph
I have a directed weighted graph $G = (V, E, W)$. There is always an edge from a vertex $i$ to another one $j$, the weight $w(i,j)$ could be positive infinity, and there does not exist any negative ...
- 237
8
votes
1
answer
1k
views
Find shortest paths in complement graph
I'm looking for an algorithm that receives as input a vertex $s$, and finds the shortest paths from $s$ to all vertices in the complement graph (undirected). The algorithm should run in $O(V+E)$ time, ...
- 339
7
votes
0
answers
400
views
Shortest path in directed graphs with no more than $\log \log n $ negative edges
Given a directed graph $G=(V,E)$ with $|V|=n$ vertices and some weight function $w\colon E\to \mathbb{R}$,
I also know that there are at most $\log\log n$ negative weight edges in $G$, and $G$ does ...
- 55
7
votes
0
answers
258
views
Correctness of a greedy Algorithm on Knockout Tournaments
You are given a function $\operatorname{rk}:\{1\dots 2^k\}\rightarrow \mathbb{N^+}$ representing the ranks of the players $1\dots2^k$ in a participating in a tournament. The tournament evolves in a ...
- 101
7
votes
0
answers
541
views
Algorithms to generate random nowhere-neat rectangulation?
I want to generate random rectangular partition of a given $m*n$ rectangle under the constraint that it must be nowhere-neat partition. Nowhere-neat partition means that a dissection of a rectangle ...
- 4,387
7
votes
0
answers
204
views
Algorithms for curve construction
I am interested in algorithms that construct continuous curves between two points in such a way that minimizes an energy functional of the curve. What sort of algorithms are most used for such tasks?
...
- 171
7
votes
0
answers
1k
views
What is the intuition behind Heap's Algorithm?
I am trying to get an intuition for Heap's Algorithm which is used to generate permutations of a given set.
What I can't understand is why if n is even the letter swapped is i and when n is odd the ...
- 223
7
votes
0
answers
376
views
How to efficiently divide a grid with some predefined sub-rectangles?
Given an $M$x$N$ grid with some predefined sub-rectangles. How to divide the grid into a set of sub-rectangles, which contains the predefined sub-rectangles, so that its the number of elements is ...
- 71
7
votes
0
answers
304
views
What's the complexity of solving a packing LP?
Linear Programming is in polynomial time weakly
(when numbers are encoded in unary).
AFAIK it remains open if it is possible to solve LP
in polynomial time strongly (when numbers are encoded in ...
- 622
7
votes
0
answers
213
views
Computing the "at least k friends in common" graph
Suppose we have the graph of a social network with symmetric connections (e.g. Facebook or LinkedIn). Suppose we would like to find all pairs of people who have at least k friends in common, in order ...
- 2,229
7
votes
0
answers
1k
views
Suurballe's Algorithm: Proof of Correctness
I was reading about Suurballe's algorithm on Wikipedia, for the shortest
edge-disjoint paths problem, i.e. given nodes $s$ and $t$ finding a pair of paths between these nodes, whose accumulated weight ...
- 478
7
votes
0
answers
477
views
How are basic feasible solutions in linear programming related to vertices in its corresponding polytope?
In Section 2.3.3 "Polytopes and LP" of the book "Combinatorial Optimization: Algorithms and Complexity" by Christos H. Papadimitriou, Theorem 2.4 establishes the relation between bfs's (basic feasible ...
- 9,441
7
votes
0
answers
431
views
Minimal covering circle
There are $n<10^4$ points on the plane. How can one approximately (with a given precision $2^{-20}$ of points' coordinates) find the minimal radius of a circle that covers some $k$ out of $n$ these ...
- 213
7
votes
0
answers
2k
views
Stopping condition for goal-directed bidirectional search for shortest path
So I have a graph and need to find shortest path between two points in it. I need1 to do it it using bidirectional search. The bidirectional search should be goal-directed, i.e. A*.
So let $l(u,v)$ ...
- 658
7
votes
0
answers
1k
views
What machine learning method for diabetes prediction SW?
I'm thinking of an application for diabetics, that, given previous values of blood glucose and insulin dosage, predicts the glucose level for the next few hours.
I know a few things about neural ...
- 243
7
votes
0
answers
166
views
Overlap Maximization problem
Here's the problem:
I have a collection of collections, $C$, where each $c\in C$ is a collection of sets $X\subset U$. Denote $c_i$ as the i-th $X$ in $c$. Informally, I want to map all the sets in ...
- 378
7
votes
0
answers
360
views
Worst-case sparse graphs for Hopcroft-Karp Algorithm
Of large sparse biparite graphs (say degree 4) with N verticies, roughly speaking, which of them cause the worst case running time of the Hopcroft-Karp algorithm? What is their general structure and ...
- 699
7
votes
0
answers
192
views
What is the proof for the lemma "For every iteration of the Gomory-Hu algorithm, there is a representant pair for each edge"?
For a given undirected graph $G$, a Gomory-Hu tree is a graph which has the same nodes as $G$, but its edges represent the minimal cut between each pair of nodes in $G$. The Gomory-Hu algorithm finds ...
- 261
7
votes
1
answer
268
views
Building cycle in rectangle
I have to build a cycle with fixed length $n$ that includes exactly $k$ corners inside $w$ x $h$ rectangle.
For example:
$w = 5\\h=3$
$n = 12\\k = 6$
I have already found out that I need at least $...
- 83
7
votes
1
answer
1k
views
Find maximum in array without comparisons between elements
Suppose $A$ is an array of integers, $|A|=n$, $A=\{a_i|1\leq a_i\leq N, i=1\ldots n\}$.
The goal is to find an efficient algorithm $\cal{F}$ to find maximum element in $A$ with these restrictions:
...
- 201
7
votes
1
answer
957
views
Fastest known algorithm for $3$-$\mathrm{Partition}$ problem
$3$-$\mathrm{Partition}$ problem is $\mathsf{NP}$-Complete in a strong sense meaning there is no pseudo-polynomial time algorithm for it unless $\mathsf{P=NP}$. I am looking for the fastest known ...
user742
6
votes
0
answers
39
views
How to find the minimum number of elements to distinguish several given sets?
Given $n$ distinct sets $S_1, S_2, \cdots, S_n$, how to find a set $X$ such that $X \cap S_1, X \cap S_2, \cdots, X \cap S_n$ are still distinct, and the size of $X$ is minimum?
For example, given $\{...
Acesrc
6
votes
0
answers
808
views
How to sort a queue using a temporary stack?
Suppose we have N natural numbers in a queue. ex queue = [3, 14, 1, 20] and an empty stack
We are allowed to make only two actions:
Action "x": Dequeue an element from the queue and push it ...
- 179
6
votes
0
answers
95
views
Scheduling tasks on a graph with assistance
This is a follow-up to a question that I recently posted here: Completing tasks on a graph. In that question, I posted the following:
Consider a graph $G = (V, E)$, where $V = \{0, 1, 2, \ldots, n\}$. ...
user127619
6
votes
0
answers
540
views
What could we say about that conjecture that yields P != NP?
Let $F$ be the set of all Boolean formulae.
We say that a Boolean formula $\varphi$ is positive (=monotone) if
$\forall \alpha\in F,i\leq n$, if $\alpha\wedge\neg x_i\models\varphi$, then $\alpha\...
- 151