Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [ds.algorithms]

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

2
votes
1answer
117 views

Is there any time efficient way of achieving the result of FKS hashing lemma?

FKS hashing lemma states. Given a set of $n-$bit numbers $\{x_1,x_2,\dots,x_k\}$ there exist a prime $p$ of $O(\log n + \log k)$-bit such that $x_i$ mod $p \neq $ $x_j$ mod $p$ if $x_i \neq x_j$...
1
vote
1answer
90 views

Minimizing SubModular Function: Cardinality

Given a submodular function f: 2^V to reals (not necessarily monotone), and an integer k, find a set S such that |S| <= k and such that f(S) is minimized. When the size constraint is |S| >=k, the ...
1
vote
0answers
58 views

What is the fastest gradient based algorithm to get to criticality of a “nice” non-convex function?

I am allowing for the following properties for a once differentiable non-convex $f : \mathbb{R}^d \rightarrow \mathbb{R}$, (a) Let there be a $\sigma >0$ s.t the norm of the gradient of the ...
5
votes
1answer
488 views

Minimum cost topological ordering

We are given a $n$ vertex directed graph $G=(V,E)$ and also given a cost function $c:V\times [n]\to \mathbb{R}$. Consider a topological ordering of the vertices, $v_1,\ldots,v_n$, the cost of the ...
9
votes
1answer
150 views

What is the fastest known algorithm for finding conjugacy classes?

Given a finite group $G$ of size $n$ by the table representation. I want to compute the conjugacy classes of group $G$. A trivial algorithm seems to take $O(n^2)$ operation ( $b = g^{-1}a g$ type ...
5
votes
0answers
165 views

Find a pair of nodes with maximum sum of distances in k given trees

For k edge-weighted trees $T_1,T_2...T_k$ which contain the same set of nodes $\{1,2,... n \}$, I want to find a pair of nodes $(x,y)$ which maxifies $$\sum_{i=1}^k d_i(x,y)$$ where $d_i(x,y)$ ...
3
votes
0answers
98 views

Graph-related applications of the fast Fourier transform (and other algebraic algorithms)

The fast matrix multiplication algorithm is useful for numerous graph problems (e.g. matchings and shortest paths). However, while the fast Fourier transform algorithm implies several other near-...
2
votes
1answer
135 views

Efficient algorithm for generating data dependency DAG from lists of memory ranges and access modes

Assume you are given: A list of N (not necessarily distinct) memory ranges of the form [x,y], where x and y are non-negative integers representing the lower and upper bounds of the range, and A list ...
2
votes
0answers
53 views

Has Khachiyan/Porkolob's convex integer optimization been implemented?

Khachiyan and Porkolab in 'Integer optimization on convex semialgebraic sets' gave an $O(ld^{ O(k^4)})$ algorithm to minimize a degree $d$ form with integer coefficients of binary length at most $l$ ...
9
votes
1answer
354 views

Is abelian group isomorphism in $\mathsf{AC^0}$?

An $O(n^2)$ running time algorithm for abelian group isomorphism is easy to see. Later working on this problem in 2003 Vikas improve the result from $O(n^2)$ running time to $O(n \log n)$. In 2007, ...
3
votes
1answer
202 views

How to compute GCD efficiently?

I want to compute $ A= \langle \text{GCD}(a,j),j=2,3,..,k-1\rangle$ and assume that each value of $j$ is less than $a$. I can compute GCD(a,j), $j=2,3,..,k-1$ and $a \le j$ for single fixed value of $...
2
votes
0answers
44 views

What is the difference between PRAM and multi threading?

PRAM and multi-threading are somewhat part of the same model of the shared memory model, in which both can compute in parallel, and both can allow processors to communicate with each other since there ...
12
votes
1answer
670 views

Is sorting $n$ real numbers in time $O(n \sqrt{\log n})$ and linear space possible?

In the recent preprint https://arxiv.org/abs/1801.00776, it is claimed that $n$ real numbers can be sorted in time $$O(n \sqrt{\log n}), $$ and linear space. The paper seems reasonable, though I am ...
14
votes
2answers
439 views

OR-circuit complexity of a dense linear operator

Consider the following simple monotone circuit model: each gate is just a binary OR. What is the complexity of a function $f(x)=Ax$ where $A$ is a Boolean $n \times n$ matrix with $O(n)$ 0's? Can it ...
3
votes
0answers
61 views

Is there some research about infinitely many-armed bandit with non-stationary assumption?

Is there some research about infinitely many-armed bandit with non-stationary assumption? I have found the paper about infinitely many-armed bandit under stationary (or stochastic) assumption. And I ...
3
votes
0answers
56 views

Finding the largest set of points of limited diameter (2)

Problem: Given a set of points $S = \{(x_1, y_1), (x_2, y_2),\cdots,(x_n, y_n)\}$ in $\mathbb{R}^2$ and a distance threshold $\tau$, find a subset of $S$ such that (1) the Euclidean distance between ...
4
votes
0answers
148 views

Is Normal centralizer problem in P? [closed]

Notations $\le$ is used for subgroup $G = \langle A \rangle $ means group $G$ is generated by set $A$ $P$ means polynomial time in input size. $\Omega = \{1,2,3,\cdots,n\}$ is a input domain Sym($\...
9
votes
5answers
634 views

Can neural networks be used to devise algorithms?

After the newer and newer successes of neural networks in playing board games, one feels that the next goal we set could be something more useful than beating humans in Starcraft. More precisely, I ...
-3
votes
1answer
114 views

Continous work distribution algorithm with failover

Imagine there's a system where there's N workers and M units of work, for example, N ≤ 64, M = 256. Is there an algorithm that ...
1
vote
0answers
122 views

Convention for RAM machine models

When algorithm asymptotic runtimes are given without explicitly noting the computational model, what is the convention for the exact model used? My understanding is that most problems use unit-cost ...
0
votes
0answers
70 views

Number of maximally different DAG's in a digraph?

Given a digraph $\overrightarrow{G}$, I'm interested in extracting all DAGs from $\overrightarrow{G}$ such that: Each DAG's vertices are differently sorted, Each DAG is maximal (adding any extra ...
2
votes
1answer
443 views

Does there exist an ontology for algorithms?

It appears that algorithmic complexity theory has already figured out Kolmogorov complexity, when applied to representations of programs themselves, can already serve as a solid theoretical metric of ...
2
votes
1answer
132 views

Computing size of permutation group from generators

You're given $k$ permutations $a_1,\dots,a_k$. Consider closure of this set under the composition operation. What are most efficient and simple algorithms to calculate the size of this closure?
0
votes
0answers
74 views

Data structures for subset and superset queries over a set of multisets

I am interested in papers discussing efficient data structures for storing and querying a set of multisets. I am particularly interested in the following two operations: Subset query: retrieve all ...
9
votes
1answer
308 views

Algorithm to compute distance between powers

Given coprime $a, b$, can you quickly compute $$ \min_{x, y > 0} |a^x - b^y| $$ Here $x, y$ are integers. Obviously taking $x = y = 0$ gives an uninteresting answer; in general how close can these ...
1
vote
1answer
90 views
3
votes
0answers
174 views

Complexity of the mandelbrot set on rationals

(Also posted on mathoverflow) Given two rationals $a,b \in \mathbb{Q}$, call $c = a + ib$, i.e., the complex number represented by these two rationals. A point $c$ is contained within the Mandelbrot ...
1
vote
1answer
341 views

Amortized analysis of red-black trees

Is there an analysis of red-black trees using amortized analysis? I saw it mentioned somewhere as an example of amortized analysis but all the proofs that I know use a global approach ("black height") ...
1
vote
0answers
56 views

\alpha-path on Euclidean graphs

Consider the following problem: Suppose we are given a G=(V, E) Euclidean Graph in the plane and a real $\alpha > 0$. For simplicity assume, there exists only one path whose summation of weights ...
-1
votes
1answer
59 views

given a set of $n$ points in $d$-dimensional space and the basis vectors of some subspace, how to find all the points on that space?

given a set $A$ of $n$ points with integer coordinates in $\mathbb{R}^d$, and $k<d$ basis vectors of a subspace $K$ of $\mathbb{R}^d$, is there an efficient algorithm that returns all points from $...
4
votes
1answer
162 views

Finding a sub rectangle with maximum sum

Given a $n \times n$ matrix filled with positive or negative numbers, find a sub rectangle with maximum sum and output the sum. There's a well-known algorithm which runs in $O(n^3)$, but can the ...
0
votes
0answers
53 views

Preference based group generator

I'm looking for a polynomial time algorithm for the following problem: $n$ number of students must be partitioned into $\frac{n - n\%m}{m}$ sets where $m$ is the ideal cardinality. Each pair of ...
4
votes
1answer
161 views

Have fixed parameter integer program algorithms ever been implemented for research use?

Have any fixed parameter integer programming algorithms described in Integer programming with a fixed number of variables been implemented? Is there a reference code that researchers can use?
-1
votes
2answers
118 views

How to continue this algorithm? [closed]

I want to create an algorithm to fill a fixed-size big rectangle (W,H) with the maximum number of fixed-size smaller rectangles (w,h) (I can rotate the small rectangles 90º). I have thought about ...
3
votes
0answers
44 views

Equal degree factoring of homogeneous polynomials over $\Bbb Q[x_1,\dots,x_n]$?

Given $f(x_1,\dots,x_n)\in\Bbb Q[x_1,\dots,x_n]$ of form $\prod_{i=1}^df_i(x_1,\dots,x_n)$ where each of $f,f_i$ are homogeneous and each $f_i$ is irreducible what is the best technique to factor such ...
8
votes
0answers
192 views

Algorithms to generate consecutive primes

The prime number theorem, states that the "average length" of the gap between a prime $p$ and the next prime is ln(p). I am looking for (preferably deterministic efficient) an algorithm that generates ...
2
votes
1answer
154 views

Is there a fast algorithm to quickly evaluate $a^{b^c}$ mod $n$?

I need to quickly evaluate $a^{b^c} \mod n$ where $c$ is pretty big. Using the usual repeated squaring trick, this can be performed in $O(\log(b^c)) = O(c)$ time. In my problem, $c$ is huge, (say, $&...
9
votes
1answer
201 views

Understanding performance of QFBV SMT solvers

SMT solvers such as Z3 or Boolector use a complex set of heuristics to solve problems. However, this also makes predicting the performance of such a solver for a given problem very hard. My question ...
-3
votes
1answer
112 views

What is wrong with this procedure to convert quadratic programming to convex quadratic programming?

Consider the feasibility quadratic program with constraint $$\sum_{i=1}^nc_{i1}x_{i}\leq \ell_1$$ $$\vdots$$ $$\sum_{i=1}^nc_{it}x_{i}\leq \ell_t$$ $$\sum_{i,j=1}^na_{ij}x_{i}x_{j}+\sum_{i=1}^nb_{i}x_{...
4
votes
0answers
488 views

Optimizing Maximum Weighted Matching (Edmonds Blossom)

Background: I've ported Edmonds Blossom Algorithm with Maximum Weighted Matching to Java: https://github.com/simlu/EdmondsBlossom/blob/master/src/Blossom.java The original Python implementation ...
1
vote
1answer
70 views

Practical/heuristic algorithm for multi set-cover

Consider a universe $N$ containing $n$ elements, and a collection of sets $\mathcal{C}$, over $N$. The $k$-multiset multicover (MSMC) problem is to cover all elements of the universe $N$ at least $k$ ...
1
vote
2answers
177 views

Check the match of the maximum of each subset

Given a number of vectors with $n$ elements, i.e., $S=(a_1, \cdots, a_n)$, $T_j=(b_1^j, \cdots, b_n^j)$ for $j=1,\cdots, m$ where each $a_i$ or $b^i_j$ is a natural number. Question: determine ...
6
votes
1answer
170 views

How to find largest supergroup in polynomial time?

Let $G \le S_n$, and G acts on set $[n]$ via a map $\pi$: $$\pi : G \times [n]\mapsto [n] $$ In Input generating set of $G$ is given. Question : I need to find the largest supergroup $G^{'}$ (...
0
votes
1answer
113 views

Different algorithms for longest increasing subsequence

The longest increasing subsequence problem has a simple and elegant $O(n \log n)$ time solution via patience sorting. Such a basic and well-studied problem, however, should have a number of different ...
4
votes
0answers
162 views

What exactly did Lenstra prove on mixed integer linear program?

I studied Lenstra's paper https://www.jstor.org/stable/3689168. I have no clue what complexity he provides on Mixed Integer Programming (it is too terse and it is not a stand alone paper as he assumes ...
6
votes
1answer
179 views

Cases of Linear programming known to be in $NC$?

Linear programming is $P$-complete. However are there special situations where we know an $NC$ algorithm?
3
votes
1answer
59 views

Complexity of Finding Optimal Synergistic Set Packings

Motivation: While developing tools for fast execution of machine learning workflows, we realized that many workflows require intermediate results -- sometimes we should cache these results, and ...
3
votes
1answer
760 views

Minimal Cost of Eulerian Path

Problem: Given a planar (undirected and mostly sparse) graph with an Eulerian Path, we introduce a cost function f: (v, e1, e2) for all two edges e1 and e2 that share a vertex v. The function also ...
0
votes
0answers
80 views

On permanent mod $3^t$ computation

By $'$ I mean transpose. I gather the info here from rjlipton.wordpress.com/2014/12/21/modulating-the-permanent. We know that if $U\in\Bbb F_{3^t}^{n\times n}$ satisfies $UU'=I_n$ in $\Bbb F_{3^t}$ ...
5
votes
1answer
273 views

Modifying Edmonds' Blossom Algorithm

Given a connected road network on an Island without one-way streets, where should I para-shoot in and what route should I take to deliver mail to all houses on the island (being picked up again by ...