Questions tagged [ds.algorithms]
Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.
1,754
questions
1
vote
0
answers
53
views
Efficient enumeration of connected functional digraphs (up to isomorphism)
Together with the research intern I am supervising, we are currently writing some software that requires us to enumerate all connected functional digraphs of $n$ vertices up to isomorphism (also known ...
3
votes
0
answers
130
views
+50
Deciding if all matrix multiplication entries have at least two witnesses
Consider two square matrices $A(x,y)$ and $B(y,z)$ of dimensions $N×N$ containing boolean entries. Consider the output product matrix $C(x,z)$ where $C=AB$ (not boolean matrix multiplication but the ...
- 1,015
-2
votes
0
answers
47
views
Reducing euclidean TSP of smaller size to euclidean TSP of bigger size [closed]
Assume I have a euclidean TSP solver that is optimal, but it can only solve inputs with exactly $N$ vertices. Let's call it the N-solver.
Now, I have an input with $K$ vertices in the 2D plane, where $...
1
vote
0
answers
66
views
Survey of Quantum Algorithms similar to Montanaro's from 2015
The survey https://arxiv.org/abs/1511.04206 by Montanaro is very nice in terms of giving a bird's eye view, which is very useful. As the author states in the abstract
Here we briefly survey some ...
- 1,986
1
vote
0
answers
21
views
Can fair ordering of transactions be achieved in permissionless blockchains?
Front running attacks mainly happen because adversaries are able to manipulate the order of the transactions on blockchains.
As many research paper address the problem of fair ordering, I don't find ( ...
- 11
0
votes
0
answers
55
views
Algorithms with advices of huge precomputed data
My main interest is complexity theory, and I'm studying the large or huge advice of Turing machines in the ongoing work.
As related to the study, I'm wondering what's known about "precomputation&...
- 689
1
vote
0
answers
22
views
Processing times of different job types on $n$ processors
I have $n$ processors that each receive an infinite sequence of jobs that have different processing times.
In the simplest case, $n = 2$ and jobs are either $\texttt{fast}$ or $\texttt{slow}$ with ...
- 131
6
votes
2
answers
237
views
How to show that the median cannot be maintained in $O(1)$ time?
Suppose that we have a stream of numbers $x_1,x_2,\ldots$ such that we wish to track the median of the values observed so far.
This task is easy to do with $O(\log n)$ update time (where $n$ is the ...
- 63
0
votes
0
answers
30
views
Multi-dimensional 0-1 Knapsack problem with a high number of dimensions
I would like to solve a multi-dimensional 0-1 Knapsack problem, by looking for approximation algorithms with constant approximation ratio if possible. Here the particularity is that the number of ...
- 101
2
votes
1
answer
171
views
Maximize a special monotone submodular function - is it easier?
I am looking for a way to optimize the function $f$, defined below.
First, fix some positive integer $k$ and let $c_1$ and $c_2$ be non-negative vectors in $\mathbb{R}^n$. Let $g$ be an increasing ...
- 557
1
vote
0
answers
45
views
Partition points in the plane
Given $n=2k$ points in the plane and also given positive real value $r$. Is there an algorithm that partition points into two groups $G_1$ and $G_2$ such that each group contains exactly $k$ points ...
- 11
0
votes
0
answers
38
views
Does the linear algorithm of Farach for sorting suffixes imply a linear algorithm for sorting a special type of a sequence of integers?
I was looking at the lecture notes on a linear time suffix trie construction algorithm by Farach and I was wondering if his suffix sorting procedure implies anything about sorting integers.
- 1
0
votes
2
answers
73
views
Find whether a 3CNF formula with every clause having either all the variables negated or all the variables non-negated is satisfiable
Given a 3CNF formula $\phi$ with the condition that, for every clause of $\phi$, either all the variables are negated or all the variables are non-negated. For example, some allowed clauses are $(x_1\...
1
vote
1
answer
139
views
Nontrivial Algorithms for Coloring (Parameterized by Pathwidth)
Let $k$ be a positive integer. In the $k$-coloring problem, we are given a graph $G$ on $n$ nodes, and want to determine if there is a way to assign a color to each vertex of $G$ such that no two ...
- 454
0
votes
0
answers
38
views
Reducing computing the partition function to computing the number of min-cardinality (s, t) cut
Consider a partition function for a graph as follows:
\begin{equation}
\mathrm{Z}_\mathrm{G}(\beta) = \sum_{z \in \{-1, 1\}^{n}} \beta^{\underset{(i, j) \in E, i < j}{\sum} w_{i,j} ~z_i z_j},
\end{...
- 153
2
votes
1
answer
150
views
Another variation of $k$-means problem in the plane
According to wikipedia,
consider $k$-means problem in the plane :
k-means clustering aims to partition the $n$ observations into $k (≤ n)$ sets $S = \{S_1, S_2, \dots, S_k\}$ so as to minimize the ...
- 23
2
votes
1
answer
129
views
Parameterized algorithm when the parameter is not known in advance?
In the setting of parameterized algorithms, we are typically given the problem instance as well as the value of the parameter.
However, it seems like in applications the value of the parameter should ...
- 557
2
votes
0
answers
167
views
Accessible entry for computational complexity theory through concrete problems
I am planning to start studying computational complexity theory. As the field is technical for a fresh undergrad alumni like me, I thought a good approach is to tackle it through areas I am more ...
2
votes
1
answer
98
views
Optimal solution for partitioning convex polygon into small pieces
Given a convex polygon $P$ (possibly) with holes. We want to partition $P$ into a minimum number of connected interior-disjoint small pieces $Q_1,...Q_s$. The definition of small can either be that ...
- 131
-3
votes
1
answer
67
views
Interesting Variation on Subset Sum Problem
Does anyone have any ideas for this algorithms problem?
Given an array $A$ with 40 integers ($-10^9 < A_i < 10^9$), how many ways are there to reach a target sum $X$.
Normally, I would use ...
0
votes
0
answers
298
views
A problem in understanding an algorithm
I read a paper from John Hershberger with this title: "Minimizing the sum of diameters
efficiently". That paper proposed a simple algorithm that finds a bipartition of points $S$ in the ...
- 194
1
vote
0
answers
29
views
How to deal with the time to minimize a function in a given interval?
I'm writing a paper in which I designed an algorithm running in $O(n^2m)\cdot T(f)$ to solve my problem, where $n,m$ is the size of input and $f:\mathbb{R}\rightarrow \mathbb{R}$ is a function, and $T(...
- 451
1
vote
1
answer
179
views
2-Center problem with forbidden pairs
Is there a nearly linear-time 2-approximation (or $O(1)$-approximation) algorithm for the following problem?
2-Center with Forbidden Pairs
input: Bipartite graph $G=(V,E)$ where each vertex $v$ is a ...
- 194
0
votes
1
answer
72
views
Is a grid graph a vertex-minor of a complete graph? [closed]
Consider a graph $G$. A graph $H$ is the vertex-minor of the graph $G$ if $H$ can be obtained from $G$ using vertex deletions and local complementations. For more information, look at Definition 2.1 ...
- 153
0
votes
0
answers
55
views
Fastest algorithm to compute maximum number of boxes that can fit inside each other
Given $n$ rectangles with widths $w_1,w_2,...,w_n$ and heights $h_1, ..., h_n$. A rectangle $i$ fits inside $j$ if and only if $h_i<h_j$ and $w_i<w_j$. We are interested in the maximum $k$ such ...
- 680
0
votes
0
answers
94
views
optimization on graph edges selection
I have the below problem. I wonder if there exists a similar known class of problems (e.g., in optimization, graph theory) which I can relate my problem to, and find a similar solution there.
I am ...
- 1
6
votes
1
answer
328
views
Complexity of optimal elimination for a planar tensor network
Edit Dec 15 it's not obvious this problem is tractable when further restricting to trees, see cs.SE question
Suppose we need to sum out variables in a tensor network (a factor graph where each ...
- 4,631
-1
votes
1
answer
110
views
Algorithm for finding traffic equilibrium
I watched a youtube video about a certain interesting property of springs and road networks. It made me think: if we represent a network of roads as a graph where edges are roads described by a ...
10
votes
0
answers
128
views
Fastest Known Algorithm to Count Acyclic Orientations in a Graph
Given an undirected graph $G$, an acyclic orientation of $G$ is choice of orientation for each edge of $G$ (turning each edge into an arc) such that the resulting directed graph has no directed cycles....
- 454
1
vote
1
answer
178
views
Young Diagrams and distinguishing between two distributions
Introduction:
The reference for everything is this paper.
The Robinson–Schensted–Knuth (RSK) algorithm is a well-known
combinatorial algorithm with diverse applications throughout
mathematics, ...
- 153
6
votes
1
answer
252
views
How can we compute the VC dimension of a finite class of sets?
Let $F$ be a class of subsets of a finite set $X$ of cardinality $n$. What is the complexity of computing the VC dimension of $F$? Can we do better than looping through every subset of $X$ and ...
- 237
0
votes
0
answers
99
views
Minimize Cumulative Cost on Topological Sort
We are given a n-vertex DAG $G=(V,E)$ and also given a cost function $c: V \rightarrow \Bbb N$.
Given a topological sort $S = v_1,v_2,...,v_n$, it has associated a sorting cost $S_c = \sum_{i=1}^{n} C(...
- 9
1
vote
0
answers
45
views
Approximate solution for maximum coverage problem with choice constraint
Suppose a sequence of sets $S_1,S_2,...,S_i$ where each set contains sets of elements. That is, each set $S$ contains many sets $a_1,a_2,...,a_{|S|}$. We are given an integer $k$ and we assume that $\...
3
votes
1
answer
191
views
Are there an algorithm that find Minimum spanning tree in $O(n^2\log\log^*n)$?
Given completed metric weighted graph $G=(V,E)$ that have $n$ vertices. Are there an algorithm that find MST of $G$ in $O(n^2)$?
I read abstract of this paper that mentioned an algorithm with running ...
- 194
5
votes
0
answers
83
views
Fine-Grained Hardness for Undirected Hamiltonicity
The fastest known algorithm for detecting Hamiltonian cycles in directed graphs on $n$ nodes runs in essentially $2^n\text{poly}(n)$ time.
However, for undirected graphs on $n$ nodes, there is an ...
- 454
3
votes
0
answers
119
views
Fastest Known Algorithm for $k$-Dimensional Matching and $k$-Exact Cover
Given a $k$-uniform hypergraph $G$ (i.e., each edge of $G$ contains precisely $k$ vertices) on $n$ vertices, the $k$-Exact Cover problem is the task of deciding if there exists $n/k$ edges in $G$ ...
- 454
2
votes
1
answer
156
views
Divide and Conquer Algorithm for 1-Median Problem
Let $P_1$ and $P_2$ be two disjoint point sets in $\mathbb{R}^d$ and $n = \vert P_1\vert = \vert P_2\vert$ and $P = P_1\cup P_2$. Let $c^\star$ be the optimal 1-median for $P$ and $opt^\star$ is the ...
- 267
1
vote
0
answers
54
views
Decision tree vs. pebble game lower bounds
This question concerns two types of lower bounds. In a pebbling lower bound, we are concerned with the complexity of constructing the output from the input. For example, if the only way we could ...
- 383
0
votes
0
answers
24
views
Fast algorithms for convex-convex quadratic fractional programming
What are the fastest algorithm(s) (possibly approximation algorithms) for solving convex-convex quadratic fractional programming problems, i.e. optimization problems of the form
$$
\begin{align*}
\sup&...
- 304
1
vote
1
answer
220
views
Is this a novel technique for determining whether or not two rotated rectangles collide?
I was trying to determine whether or not two rectangles rotated around their centers were colliding and randomly thought to try the following algorithm:
Rotate both rectangles by the negative rotation ...
- 37
0
votes
2
answers
310
views
Partition a graph into two clusters
Suppose given a complete weighted graph $G=(V,E)$, with positive weight. Are there an algorithm that partition $G$ into two clusters $C_1,C_2$ such that sum of heaviest edges in $C_1,C_2$ minimized?
...
- 194
2
votes
0
answers
93
views
How typical are odd-H-minor free graphs?
Can anything be said about how typical are odd-H-minor free graphs? (definition of odd-minor-free is in Section 2.2 of notes, page 20 of slides). For instance, for a random graph with $n$ vertices, $...
- 4,631
0
votes
0
answers
19
views
Fast filter for concurrent version vectors (vector clocks, lamport clocks) from a set
I have a set of version vectors (or vector clocks) and need to implement a filter function that takes this set and returns a new set where all elements are either "equal", "happened ...
- 101
0
votes
1
answer
121
views
Max-k-cut with negative edge weights
Let $G=(V,E,w)$ be a graph and for edge $e\in E$, there is associated weight $w_e$.
The max-k-cut wants to partition V into k subsets $P_1,\cdots,P_k$ and maximize $\sum_{1\leq r<s\leq k}\sum_{i\in ...
7
votes
0
answers
321
views
Problem in the paper "Stable Minimum Space Partitioning in Linear Time"
The paper Stable Minimum Space Partitioning in Linear Time describes an algorithm that stably sorts a binary array (an array whose elements can only have two distinct values) in $O(n)$ time complexity ...
- 121
1
vote
0
answers
75
views
Parametrization of context-sensitive language in polynomial time
Let $\Sigma$ be a finite alphabet. Let $L\subset \Sigma^*$ be a context-sensitive language containing a word of every length.
Can we always find $f:\Sigma^*\to L$ computable in polynomial time in ...
- 11
0
votes
1
answer
55
views
Set cover where consecutive sets differ by at most one item [closed]
First I define my version of the set cover problem: We have a collection of sets such as $S_1, \dots, S_m$ where each $S_i$ is a subset of $M=\{1,\dots, m\}$. The goal is to find the minimum number of ...
- 230
0
votes
1
answer
53
views
How to build the tree with the "most different" solutions of a clustering?
Illustrate the question with an example : we have a similarity matrix for 1000 people, and the similarity represents how much their hobbies are the same (it does not really matter how it's built).
Let'...
- 109
2
votes
0
answers
148
views
Theorem on non-decreasing probability of success of an algorithm
Question: What's a standard name/framework for the following, or some variant?
Stated briefly for a probabilistic algorithm: define $p_n$ as the conditional probability of success of a fork of the ...
- 109
9
votes
3
answers
266
views
Sublinear Time Regular Expression Search
Does there exist a data structure with the following properties. Given a string $s$, it performs some polynomial amount of precomputation to construct the data structure. After construction, it allows ...
- 91