Questions tagged [ds.algorithms]

Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.

Filter by
Sorted by
Tagged with
0
votes
0answers
15 views

Remove cycles from a stochastic comparison matrix, while doing the least amount of editing

Let $\mathcal P_n$ be the collection of all matrices $M \in [0, 1]^{n \times n}$ such that $M_{ij} + M_{ji} = 1$ for all $i, j \in [n]$. Such matrices are called comparison matrices. A comparison ...
-3
votes
0answers
73 views

Is this case possible for the P/NP problem? [closed]

I was wondering if the following could be a possibility in the resolution of the P=NP problem. Could it be that every algorithm(except one) for any NP complete problem is exponential in the general ...
-4
votes
0answers
34 views

Time complexity of counting the non-prime numbers

So i have a code that i need to find (and proof) the time complexity of it: For ( i = 2 -> N ) For ( j = 2-> sqrt(i)) If(i%j==0) K++ Break; Would really appreciate if someone can help.
2
votes
0answers
82 views

Is there a competitive algorithm for this online scheduling problem to minimize the truncated gaps?

Time is discrete. There are $n$ time-slots and a single job that can be scheduled on one machine of budget $B$. If the job is scheduled at time-slot $t$, then it will consume $c(t)$ units of the ...
19
votes
1answer
1k views

Has parameterized complexity led to better algorithms?

I know that for the vertex cover problem, if we know that the parameter $k$ (which is the number of vertices in the solution) is small, then we can expect to solve it feasibly in practice. So far, ...
-1
votes
0answers
34 views

Is this some variant of online knapsack problem?

We have a set of $n$ bins with capacities $c_1, c_2, \cdots, c_n$. Now, I have items arriving in one by one with arbitrary sizes. I want to place the item in the bins in the following manner: The ...
4
votes
0answers
76 views

Complexity of Encoding a Matroid Flow Problem in a Matrix

Context: Take a directed graph $G$ with a specified subset of source vertices $S$ and target vertices $T$. We say a subset $I\subseteq T$ of size $r$ is independent if there exist $r$ distinct ...
18
votes
0answers
356 views

In an $m$ by $n$ Boolean matrix, can you find a square block whose four corners are ones in $O(m \cdot n)$ time?

Decision Problem Input: An $m$ by $n$ Boolean matrix $M$. Decision Question: Does there exist a square block within $M$ such that upper-left corner entry == upper-right corner entry == lower-left ...
0
votes
1answer
46 views

Algorithm to calculate coordinated radio frequencies

I'm stuck on this algorithm problem for a project I'm working on. I can find no relevant documentation, and would very much appreciate any help that can be offered on this! I will try to explain it ...
0
votes
0answers
97 views

Algorithms and approximations for optimal offline binary tree operations

Let's say we are using a binary tree to represent a set of elements, with operations $\mathsf{insert}(x)$ and $\mathsf{delete}(x)$. We will assume that the operations are used such that a deleted ...
5
votes
1answer
77 views

Generate cut $(A,B)$ in edge-colored graph $(V,E_1 \cup E_2)$ such that there are more red than white crossings, i.e $|E_1(A,B)| > |E_2(A,B)|$

Let $G=(V,E)$ be graph. Recall that a cut of $G$ is (or can uniquely be identified with) a pair $(A,B)$ of nonempty subsets of $V$ which partition it. Given a cut $(A,B)$, let $E(A,B) := \{(a,b) \in ...
4
votes
0answers
292 views

Deciding whether $2^k+m$ is prime

I thought something fancy can be done with number-theory or memoization, but neither worked for me. Being limited in knowledge I decided to ask experts. Does there exist a deterministic polynomial-...
1
vote
0answers
44 views

Reference request: algorithm meta-analyses

Could you direct me to papers that survey families of algorithms? The ideal paper would focus on a single family of algorithms, would show how the improvements in each algorithm work, and ideally ...
3
votes
1answer
175 views

How can I optimize my brute-force solution to this problem?

I am working on a solution to the problem explained below. I am using brute force, I have reached the point where solutions are prohibitive, so I need to optimize more (if possible). Of course, it ...
3
votes
1answer
122 views

Maximum subarray problem with weights

The maximum sum subarray problem involves finding a contiguous subarray with the largest sum, within a given one-dimensional array $A[1...n]$ of numbers. Formally, the task is to find indices i and j ...
3
votes
1answer
126 views

Polynomial evaluation at all different points

I have a polynomial $f(x_1,\ldots,x_{50})$ of 50 variables over binary field $GF(2)$. I want to evaluate at all $2^{50}$ points and check how many of them are 0. Ofcourse we can evaluate at all ...
3
votes
0answers
93 views

On solving Planar Circuit SAT

This enquiry is three-sided. Side 1 - State of the art Which is the best known algorithm for $\text{PLANAR-CIRCUIT-SAT}$? Which is the best known algorithm for $\text{PLANAR-CIRCUIT-SAT}$ assuming ...
5
votes
1answer
169 views

Complexity of finding the most likely edge

Consider a connected, unweighted, undirected graph $G$. Let $m$ be the number of edges and $n$ be the number of nodes. Now consider the following random process. First sample a uniformly random ...
2
votes
0answers
49 views

The Edge Cover Equilibrium Problem

Let the Edge Cover Equilibrium Problem be the following: INPUT: a simple undirected graph $G$. OUTPUT: YES, if the number of edge covers of $G$ having odd cardinality is equal to the number of edge ...
2
votes
0answers
94 views

What's the constant coefficient of the Coppersmith-Winograd algorithm?

Every source I can find just says "too big to be practical."
3
votes
2answers
150 views

Match a string agains a set of regexes

There are several algorithms to match a (simple) string against a regular expression (see here). But if we have a lot of regexes, can we find one of them that matches the given string faster than ...
3
votes
2answers
149 views

Complexity of Set Difference

Given $k$ sets $S_1$, $S_2$, $\dots$, $S_k$ in the universe $U = \{1, 2, \dots, n\}$, is there a way to preprocess the $k$ sets such that there is an output-sensitive query algorithm that computes $...
6
votes
2answers
443 views

Implication of solving 3SUM problem of a certain size on the Exponential Time Hypothesis

In the recent question 3SUM Complexity—A special(?) Case I asked about why the set size $O(n^3)$ was an interesting value for the 3SUM Problem and got a nice answer. My reference was the paper “...
6
votes
2answers
278 views

3SUM Complexity—A special(?) Case

In the paper “Consequences of Faster Alignment of Sequences” by Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann which appeared in ICALP 2014 and is available here the following version of ...
1
vote
1answer
147 views

What is the complexity of this submatrix selection problem?

We have a $kn\times kn$ matrix $M$ made of $n^2$ many $k\times k$ blocks. We want to find an $n\times n$ submatrix such that each row and column is from distinct window of size $k$ such that the sum ...
0
votes
1answer
100 views

Minimizing the gaps with incremental capacity

There are a single job, a machine and a set of $n$ slots. The machine has a capacity that increments by $\zeta(t)$ every slot $t=1,2,\ldots,n$. Initially (before the first slot), the machine has 0 ...
2
votes
0answers
65 views

Is there a fast algorithm for computing the Schmidt decomposition

I have a huge covariance matrix, 𝑀, with the dimension, e.g., $10^8 \times 10^8$. Luckily enough, the number of nonzero eigenpairs, $n$, is very small, i.e., $n<5$. From the computational ...
0
votes
0answers
182 views

Add edges to a DAG to maximize increase in number of connected vertices

Let $G$ be a Directed Acyclic Graph. $$C(G) = \bigl|\{(u,v):u,v\in V(G),v \text{ reachable from } u\}\bigr|$$ Goal is to add $k$ edges in a DAG such that for the new $G'$, $C(G')$ is maximized. ...
-1
votes
1answer
96 views

Required sample size to hit certain subset of a ground set

Suppose $X$ is a set of $n$ points in $\mathbb{R}^d$ and $N_1,\cdots,N_k$ are k disjoint (unknown)subsets of $X$. There is a probability distribution $\phi$ on $X$ defined as $\phi(p) = \frac{\lvert\...
0
votes
0answers
42 views

understanding generalized coupon collector for distributions or learning mixture of distribution

Lets suppose we have a set $S=\{1,\ldots,n\}$ and $P$ is the uniform distribution over two subsets $T_1,T_2\subseteq S$, each of size $m\leq n/100$. Now, suppose somehow is given uniform samples from ...
2
votes
0answers
60 views

Complexity of computing Earth Mover's Distance when the costs satisfy the triangle inequality

Let p and q by two categorical probability distributions over $\{1,2,...,k\}$. Given a set of costs $c_{ij} \ge 0, i,j \in \{1,2,...,k\}$ that satisfy the triangle inequality, that is $c_{ij} \le c_{...
0
votes
0answers
88 views

NP-Hard or PTIME?

I am working on my research problem that essentially boils down to the following question. Consider an $N \times N$ matrix. There is a man at given a starting point $(x,y)$. In each unit of time, the ...
6
votes
2answers
309 views

On the complexity of a “list” datastructure in the RAM model

I am interested in the complexity of a data-structure equipped with the following operations (similar to a list): insertion of an element at a given position within the list deletion of an element at ...
3
votes
1answer
74 views

Interval partitioning with restrictions: NP-complete or efficiently solvable?

The interval partitioning problem can be solved efficiently using a greedy algorithm. However, adding restrictions on the interval assignment to the problem results in a problem that appears harder. ...
1
vote
0answers
24 views

Are the intermediary sets in maximum cardinality search optimal in some way?

The maximum cardinality search (MCS) algorithm works as follows. Given a weighted graph $G = (V, E)$ where $w(u, v)$ denotes the weight of the edge $\{u, v\}$, we select a start node $a \in V$ and do ...
-3
votes
1answer
51 views

Finding a non-negative solution to an integer system of linear equations

Let $A$ be an $n \times m$ integer matrix and consider the system of equations $Ax = b$ where $b$ is an integer vector. I want to find a solution $x$, assuming one exists, such that the components of $...
3
votes
1answer
113 views

What is the complexity of this weighted b-edge matching problem?

I'm wondering about the complexity of the following variant of the Generalized Weighted b-edge Matching problem: Input: An undirected multigraph $G = (V, E)$ without loops, an edge partition $(E_1,...
0
votes
1answer
266 views

Time complexity for multiplying two lower triangular matrices

I was wondering, if multiplication of two $n \times n$ lower (or upper) triangular matrices has a more efficient algorithm than multiplication of two general $n \times n$ matrices? $$ \begin{bmatrix} ...
5
votes
0answers
84 views

Optimal point placement on integer lattice

What is known about the following point placement problem? For positive integers $N$, $n<N^2$, and $N\times N$ grid $\mathcal{G}$, compute \begin{eqnarray*} \mu_1(N,n)\triangleq\min_{\mathcal{P}\...
7
votes
0answers
133 views

Subgraph isomorphism on graph sequences

I'm looking for a subgraph isomorphism algorithm that takes advantage of properties of graph sequences. Say $\{G_i\}_{i=1}^k$ is a sequence of graphs on vertex set $\{1 ... n\}$, and two consecutive ...
0
votes
0answers
30 views

Best known bounds on feedback arcset in high-girth directed graphs?

I asked this question over at MathOverflow, but thinking about it a little more I think it is a more natural fit here. Let $G$ be a directed graph with $n$ vertices and $m$ edges such that every ...
1
vote
1answer
68 views

Running an algorithm for fixed amount of time on RAM model machine

Suppose there is a deterministic algorithm of size $O(1)$ that operates on an input of size $N$ on a RAM model machine. I want to run the algorithm for $O(\sqrt{N})$ time, pause the algorithm, print "...
0
votes
0answers
47 views

Can we multiply two numbers more efficiently (using binary circuits) if one of the numbers is fixed? [duplicate]

Let $a_1, a_2 \dots$ be a sequence of natural numbers, where $a_i$ has bit length $i$. Consider a function $f_n : \{0, 1\}^n \to \{0, 1\}^{2n}$ defined as $f_n(x) = a_n \cdot x$ ($\cdot$ is ...
1
vote
0answers
65 views

Combinatorial problems in electronics

This could be a downvoted question but I am asking because I am not able to get usable info via Google. Are there any interesting combinatorial problems in the field of electronics circuits design? I ...
2
votes
1answer
99 views

Are string palindrome questions practically interesting?

I've been reading Don Gusfield's "Algorithms on Strings, Trees, and Sequences", and quite a some chunk of the textbook concentrates on palindromic-related ideas. I'm unsure as to whether this is ...
9
votes
0answers
126 views

Is Gödel's speed-up theorem an instance of Blum's speedup theorem?

Blum's speedup theorem is a statement about a certain class of computable functions for which it is always possible to find a faster algorithm. Gödel's speed-up theorem is a statement about the ...
0
votes
0answers
16 views

Why is it more efficient to merge larger runs higher in the tree than perform a balanced tree of merges in an unbalanced ping-pong merge?

While studying the research paper published by Microsoft in 2014, I stumbled upon Unbalanced Ping-Pong Merge. In section 3.2 of the paper, it discusses about merging two sorted runs at a time. It ...
3
votes
3answers
463 views

Best parameterized algorithm for maximum clique

I have seen the basic algorithm for the maximum clique problem parameterized by the maximum degree at an algorithms course. However, I struggle to find anything better. Searching for things like "...
2
votes
0answers
268 views

Time Complexity for Nearest Neighbor Searches in kd-trees

Nearest neighbor searches in kd-trees run in logarithmic time, as shown by Friedman et al. However, I have some difficulty to fully understand the proof. In order to calculate the average number of ...
3
votes
1answer
142 views

Convex polygons inclusion relation

I have the following problem which came as a subproblem in some work I was doing and I am completely stuck. Note that I am interested in it only in terms of worst case time complexity (not heuristics ...

1
2 3 4 5
34