Questions tagged [ds.algorithms]
Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.
1,795
questions
1
vote
0
answers
24
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
71
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
25
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
283
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
38
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 ...
- 113
2
votes
1
answer
199
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 ...
- 597
1
vote
0
answers
48
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
2
answers
112
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
179
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 ...
- 484
2
votes
1
answer
162
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
3
votes
1
answer
148
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 ...
- 597
2
votes
0
answers
175
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 ...
-3
votes
1
answer
77
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
304
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
38
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
187
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
85
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 ...
- 173
0
votes
0
answers
57
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 ...
- 897
0
votes
0
answers
118
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
346
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,661
-1
votes
1
answer
112
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
141
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....
- 484
1
vote
1
answer
184
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, ...
- 173
6
votes
1
answer
298
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 ...
- 247
0
votes
0
answers
151
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
51
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 $\...
user53330
3
votes
1
answer
271
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
93
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 ...
- 484
4
votes
0
answers
169
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$ ...
- 484
2
votes
1
answer
182
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 ...
- 265
1
vote
0
answers
64
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 ...
- 693
1
vote
1
answer
244
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
351
views
Partition a graph into two clusters
Suppose given a complete weighted graph $G=(V,E)$, Is 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?
Note that, heaviest edge ...
- 194
2
votes
0
answers
97
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,661
0
votes
1
answer
168
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
1
answer
399
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
79
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
62
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
58
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
164
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
279
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
2
votes
0
answers
165
views
Triangle detection hardness in regular graphs
Consider a tripartite graph over $n^{1-\epsilon}$ vertices each in sets $I, J, K$. Suppose we impose a constraint that every vertex has degree $n^\epsilon/c$ for some constant $\epsilon > 0$ and ...
- 1,177
1
vote
2
answers
219
views
Finding the point that maximizes a linear function
Consider $N$ two-dimensional points of the form $(x_i, y_i)$ where all $x_i, y_i > 0$ are positive integers. We will be given a workload of queries $Q = \{c_1, \dots, c_k\}$ where for each $c_j \in ...
- 1,177
2
votes
1
answer
131
views
Do there exist two equivalent objective functions one of which can be approximated but another one cannot?
I have two equivalent problems A and B, meaning that the optimal solution of one must be the optimal solution of another one. However, it seems that problem A can be approximated but B cannot. Below ...
user53330
4
votes
0
answers
86
views
Flipping one bit to maximize BMM output
Consider a boolean matrix $A$ of size $N \times N$ and let $A^\top$ be its transpose. Let $C = AA^\top$ be the boolean matrix multiplication (BMM) result and let $c$ be the number of non-negative ...
- 1,177
1
vote
1
answer
199
views
Finding output with unique witness in matrix multiplication
Consider two square matrices $A(x,y)$ and $B(y,z)$ of dimensions $N \times N$ containing boolean entries. Consider the output product matrix $C(x,z)$ where $C = AB$ (not boolean matrix multiplication ...
- 1,177
3
votes
1
answer
358
views
How hard is this combinatorial optimisation problem?
Suppose we have multiple intervals $R_1,R_2,...,R_i$ of non-negative integers. These intervals may overlap and we use $R_h(\mathrm{median})$ to denote the median integer in the $h$-th interval $R_h$, ...
user53330
2
votes
1
answer
210
views
Characterization of integral polyhedra
A rational polyhedron $P \subseteq \mathbb{R}^n$ is an integral polyhedron if it is the convex hull of its integer points. That is, if $P = conv(P \cap \mathbb{Z}^n)$.
Equivalently, $P$ is integral if ...
- 597
16
votes
4
answers
3k
views
Algorithms Careers
I’ve been writing software for a living for a number of years now. I have graduate background in mathematics and I am wondering whether knowledge of higher algorithms is utilized anywhere in industry. ...
- 301
5
votes
0
answers
441
views
How to find the second smallest cut in a graph?
For an undirected graph, how do we find the second smallest $s,t-$cut(s) for some $s,t\in V$? What's the time complexity of this computation? What if we only cared about finding a cut of size $p+1$, ...
