Questions tagged [ds.algorithms]
Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.
1,868 questions
0votes
0answers
56views
Heuristic for Solving 3-SAT Based on Literal Sign Analysis and a Correction Phase
I am trying a heuristic approach for solving 3-SAT instances without backtracking. The method relies on an initial variable assignment based on literal signs, followed by a targeted correction phase ...
1vote
1answer
79views
Why isn't the time complexity of union-find (using disjoint-set forests) linear?
Sorry if the question appears a bit provocative; what I'm really looking for is help in finding where the error is in the following argument. [ETA: I think I've found the source of my error. Tarjan ...
- 31
0votes
0answers
99views
Is my data structure for this computational geometric problem correct?
This problem comes up as a subproblem in an area that is usually considered distant to computational geometry. Since computational geometry is not my specialty I would like to ask you if you think my ...
- 11
2votes
0answers
83views
How fast does a Swiss tournament sort?
The main idea of a Swiss tournament is that in each round players with a similar score play each other. This question is about how efficient such a tournament is to sort. More formally, assume that ...
- 14.4k
1vote
0answers
52views
What are the state-of-the-art algorithms for maintaining the dynamic upper envelope of a set of linear functions?
I am looking for information on the state-of-the-art algorithms and data structures for the dynamic upper envelope problem. Let F = {f₁, f₂, ...} be a set of real-valued linear functions defined over ...
- 11
5votes
1answer
177views
Find pair of vectors from a set with the greatest dot product
Given $X \in \mathbb{R}^{n \times d}$, output $(i, j) \in [n]^2$ with $i \neq j$ that maximizes $X_i \cdot X_j$. Beyond the trivial $\Theta(n^2 d)$ algorithm, what are the fastest known algorithms for ...
- 732
1vote
0answers
63views
Repeated subgraph matchings with disjoint images
I'm having trouble finding the name (if it exists) of a particular specialization of the subgraph enumeration problem where subgraphs isomorphisms have disjoint images. More specifically, let $G = (V, ...
1vote
0answers
70views
Are there any natuarlly occurring problem having an algorithm with run time O(n^d) with d > 10? [duplicate]
Are there any naturally occurring polynomial time solvable problem with degree of the polynomial greater than 10 ? The closest I found is AKS's Primality algorithm with runtime $\tilde{O}(n^{12})$ but ...
- 111
1vote
1answer
47views
Interpretation of P2C invariant in Paxos Made Simple?
In Paxos made simple, invariant P2C is given: ...
- 11
0votes
0answers
102views
Understanding a remark on O(log d) ratio for Online Set Cover
In the paper "The Online Set Cover Problem" by Alon, Awerbuch, Azar, Buchbinder and Naor, they study an online version of the set cover problem in which elements arrive one by one and ...
- 649
0votes
1answer
149views
How can I calculate a hash for a set of natural numbers
I have a large set of natural numbers and I want to compare it with another set of natural numbers just to determine if they are the same or not. Essentially, what I want is to calculate some sort of ...
0votes
0answers
123views
What’s the minimum number of moves needed to win the Google snake game?
So I’ve been obsessing over this for a while now and could really use some help. I’m trying to figure out the minimum number of moves it would take to win the Google Snake game if you played perfectly....
4votes
1answer
205views
About the negative real weight SSSP in $\tilde{O}(m n^{8/9})$ by Fineman
In his sensational paper “Single-Source Shortest Paths with Negative Real Weights in $\tilde{O}(m n^{8/9})$ Time”, (STOC ’24), Jeremy T. Fineman successfully broke the long-standing bound of negative ...
- 143
0votes
0answers
106views
$\mathsf{GCD}(a,b)\not\in TC^0$ while fixed dimension feasibility $ILP$ is in $TC^0$ consistent with our knowledge?
The reduction from $\mathsf{GCD}(a,b)$ is to do binary search on the feasibility of program $$r_1<au+bv<r_2$$ $$u,v\in\mathbb Z$$ where $a,b$ are given integers and we do binary search with ...
- 13.5k
0votes
0answers
49views
Min cost perfect matching, but with conflicting edge pairs
Consider the following variant of min-weight perfect matching. We are given a graph $G = (V,E)$ with non-negative weights on the edges. We are also given a collection of pairs of edges $P \subseteq E \...
- 649
