Questions tagged [ds.algorithms]
Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.
466
questions with no upvoted or accepted answers
3
votes
0
answers
46
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 ...
- 12.8k
3
votes
0
answers
152
views
Efficiently computing the union of all minimal unsatisfiable constraint sets in a first-order unification problem
Suppose we are given a standard first-order unification problem, represented as a set $D$ of term equality constraints, such that the system $D$ as a whole is unsatisfiable. Consider the minimal ...
- 236
3
votes
0
answers
118
views
Restricted k-set cover is in NL or L
Restricted $k$-set cover:
Input: $(U,S_1,S_2,\cdots, S_n, k)$, $U=[n]$ and $S_i\subseteq U$ for all $1\leq i \leq n$.
Output: $\bigcap_{i\in I}S_i$ where $I=\{1,i_1,i_2\cdots,i_k\},
i_1=min(S_1),i_2=...
- 175
3
votes
0
answers
105
views
Notion of "total work" of a problem?
I apologize in advance if this question is outside the scope of this Exchange community; if so, perhaps someone can point me in the right direction.
I am curious if there is a theoretical notion of "...
- 131
3
votes
0
answers
263
views
A sequence wherein the Kolmogorov complexity of the terms does not increase
I am looking for an algorithm $A$ - which for any non-null input string $s_1$ produces a sequence $s_1, s_2...$ such that :
It can be proved in some axiomtic system $S$ that: $\...
- 405
3
votes
0
answers
117
views
Factorizing semiprime $n=pq$ with $p \mid q-1$
Could we find a fast integer factorization algorithm for any large semiprime $n=pq$, if we know that $p \mid q-1$?
- 131
3
votes
0
answers
380
views
Approximating the VM packing problem
In the wikipedia article on bin-packing it is stated that
A variant of bin packing that occurs in practice is when items can share space when packed into a bin. Specifically, a set of items could ...
- 1,096
3
votes
0
answers
181
views
Finding median in a changing array
Consider the problem of needing to support an $n$ integers array structure with two operations:
Set(k,v) - set the $k$'th integer to value $v$ (i.e. $A[k]=v$).
Median() - return the median value of ...
- 9,438
3
votes
0
answers
154
views
Exactly solvable but non-trivial integrality gap
Are there interesting polynomial time solvable problems that we know of for which the natural convex relaxation has a non-trivial integrality gap?
Note: Maximum matching doesn't qualify because I ...
- 6,970
3
votes
0
answers
108
views
Online bridge and nonbridge counting (identification)
I was wondering if there is any efficient (possibly armortized poly-logarithmic) online algorithm which supports counting (identification) of bridges- and non-bridges online, i.e. during a sequence of ...
- 51
3
votes
0
answers
179
views
Algorithm (parallel and serial) for Gram-Schmidt
Suppose we are given $m$ vectors $v_1, \dots, v_m$ in $n$-dimensional space $\mathbf R^n$ (or perhaps they are specified up to $b$ bits of precision). I would like to find an orthonormal basis for the ...
- 3,488
3
votes
0
answers
200
views
Election algorithm with unreliable messages and a certain timestamp
I am struggling to get a correct algorithm for a leader election algorithm in a distributed system. My assumptions are as follows:
Messages are sent unreliably with an at-most-once sending
Nodes are ...
- 31
3
votes
0
answers
162
views
Multi-Agent Pathfinding
Quoting from Wang and Botea 2011:
An instance is characterized by a graph representation of a map, and a non-empty collection of mobile units $U$. Units are homogeneous in speed and size. Each unit $...
- 1,132
3
votes
0
answers
183
views
Building a "balanced" universal set
A set of length $n$ binary vectors $\mathcal{U}=\{u_1,..,u_r\}$ is called $(n,k)$-universal if for all $S\subset [n], |S|=k$, $|\mathcal{U}_{|S}|=2^k$, i.e. for every subset of indices of size $k$, ...
- 9,438
3
votes
0
answers
965
views
What's the hardest problem with a non-trivial exact algorithm?
Exact algorithms for NP-complete problems are sometimes feasible, if the input is small enough.
I’ve also came across some algorithms which are not practical even for very small inputs, and their ...
- 9,438
3
votes
0
answers
267
views
Atomic snapshot algorithms on tree-structured shared registers
Background:
Atomic snapshot memory is a shared memory partitioned into words written (updated) by individual processes, or instantaneously read (scanned) in its entirety.
The Gang of Six algorithm ...
- 2,329
3
votes
0
answers
99
views
Constant time search for rod segment
(I tried to ask at SO but maybe this has more to do with the CS theory.)
Suppose I have a rod which I cut to pieces. Given a point on the original rod, is there a way to find out which piece it ...
- 289
3
votes
0
answers
217
views
Proving greedy algorithm is optimal for a scheduling problem
First, the problem discription:
For a sequence of $4n$ tasks, $a_1a_2\dots a_{4n}$, where $a_i\in\{0,1\}\forall i$, put them sequentially to the tail of one of the two initially empty queues of ...
- 131
3
votes
0
answers
204
views
Open questions about linear-time
What are some interesting open or solved-but-hard questions around problems having linear-time solutions? Ala riffle shuffles.
I'm especially curious about problems which people believe to be linear-...
- 1,206
3
votes
0
answers
134
views
Linear programming - How to allow cycles with weight at most s?
Consider a graph $G=(V,E)$ with nonnegative weight function on the edges $w$.
How would you express in LP that you want to allow cycles in $G$ with total weight at most $s$ ?
I've found this while ...
- 131
3
votes
0
answers
272
views
Maximizing a convex function where the objective function is separable but the search space is not
The problem statement is
Given convex functions $f_i$ over $X$, find $$\arg\max_{x\in X} \sum_i f_i(x)$$
Does this kind of problem structure allow one to use specific strategies to solve the ...
- 261
3
votes
0
answers
205
views
Randomized rounding on a graph
Assume we are given an arbitrary undirected graph $G = (V, E)$ where $|V| = n$. We are also given real numbers $x_e \in [0, 1]$ for each $e \in E$. These numbers satisfy the following constraint:
\...
- 181
3
votes
0
answers
46
views
Polyhedral embedding from graph degree sequence
Given: A degree sequence.
Wanted: A graph and a polyhedral embedding of this graph (described by a rotation system or something equivalent). By polyhedral embedding I mean only the combinatorial ...
- 669
3
votes
0
answers
75
views
Load-balancing; Alternate methods of keeping track of nodes?
Reading various articles in the literature have given me only a few decent methods of keeping track of nodes before->after load-balancing them on a very large network.
One popular method uses virtual-...
- 131
3
votes
0
answers
173
views
Partitioning the vertices of a complete graph with weights on both vertices and edges with constraints
Given the complete graph on n vertices. Each vertex and each edge has a positive weight associated with it. What is desired is to partition the vertices into parts so that the sum of the weights of ...
- 96
3
votes
0
answers
626
views
K-shortest path in large sparse graph
I am an engineer and looking for a reference to find k-shortest path's in a large sparse graph. In the search for it, I came acorss Yen's ranking loopless algorithm and an improved implementation of ...
- 185
3
votes
0
answers
153
views
minimizing makespan for related machines
Any reference is appreciated.
There are $n$ jobs and $m$ machines, machines has speeds and jobs have processing times. It takes $p_j/s_i$ units of time for machine $i$ with speed $s_i$ to process job ...
- 1,443
3
votes
0
answers
288
views
Distinguishing two types of Monte-Carlo algorithms
Recall from Wikipedia that Monte Carlo algorithm is a randomized algorithm whose running time is deterministic, but whose output may be incorrect with a certain (typically small) probability. Consider ...
- 763
3
votes
0
answers
191
views
Separation Oracle for Inverse Bipartite Matching Polytope
The $N$x$N$ bipartite matching problem can be written as finding a configuration of variables ${\mathbf y}^* = \{y^*_1, \ldots, y^*_N\}$, $y_i \in \{1, \ldots, N\}$ such that
$${\mathbf y}^* = \arg\...
- 681
3
votes
0
answers
223
views
The Quality of SDP relaxation on MaxCut
My question is: given a maxcut instance, if it costs too much to solve it to optimal practically but we can get an optimal solution of SDP relaxation quickly, can we assess the quality of this SDP ...
- 31
3
votes
0
answers
112
views
Sampling from a distribution with a given covariance matrix
Let $\bf X$ be a binary vector of $n$ (non-independent) random variables $X_1,\ldots, X_n$.
Covariance of two random variables is defined as follows: $$\mathrm{cov}(X_i, X_j) = \mathrm{E}(X_i - \mu_i)...
- 251
3
votes
0
answers
330
views
Taking Square Roots of Matrices over Z/nZ
Is it easy (computationally) to take square roots of matrices over Z/nZ, if you know the factorization of n? More specifically, suppose I generate a random matrix M, and square it. Can a ...
- 331
3
votes
0
answers
159
views
Gram matrix of Max-Cut relaxation
It seems that Goemans and Williamson give a unique representation for each graph of the semidefinite relaxation (elements $y_{ij}$ of Y). However, semidefinite programming may give the same maximum ...
- 573
3
votes
1
answer
2k
views
Finding the nearest node to a given set of nodes in a graph
I am looking for an algorithm that, given a large weighted undirected graph, would find the node that has minimum average distance from a given set of nodes in the graph.
- 139
2
votes
0
answers
36
views
Generalization of Binary Decomposition to Polynomials?
Given an integer $x\in\mathbb{Z}$, we can write its binary decomposition (and more generally base $B$ for $B\in\mathbb{Z}$, $B>1$) as
$$x = \sum_{i=0} x_i B^i,$$
where $x_i \in \mathbb{Z}/B\mathbb{...
- 918
2
votes
0
answers
42
views
Effective algorithms for finite lattices of (higher-order) monotonous functions?
I am looking for references on effective algorithms on finite lattices or posets, and in particular on lattices of monotonous functions between two lattices, with higher-order structure -- monotonous ...
- 2,040
2
votes
0
answers
103
views
Is there a calculus or formalism for measuring set relations between algorithm outputs?
I'm asking this question from a fairly naive position, so apologies in advance, etc.
I'm aware of the Bird-Meertens formalism for equational reasoning about algorithms but what I'm really interested ...
- 121
2
votes
0
answers
66
views
Confusion with the definition of Online Set Cover
I am confused on a technicality on how Online Set Cover is defined.
One way to define it is: We are given a collection of sets $\mathcal{S}$ upfront, and in each time-step an element arrives to be ...
- 607
2
votes
0
answers
43
views
Algorithms for parametric matroid optimization
Let $M$ be a rank $r$ matroid with basis set $\mathcal{B}$ and an independence oracle. Given a linear function $w_e$ on each element $e$ of the matroid, we want to find the minimum weight basis for ...
- 4,367
2
votes
0
answers
76
views
Has there been any research on faster tensor inner products?
Matrix multiplication is a well studied problem which is recently back in the news due to deepmind.
That got me wondering has anyone looked at the more general problem of faster tensor multiplication? ...
- 369
2
votes
0
answers
120
views
Open problem on *Finite Memory Clocks* by Tom Cover
This problem was proposed by Tom Cover in Open Problems in Communication and Computation (Cover and Gopinath, eds), 1987:
How does one tell time when the number of states in the clock is
insufficient ...
- 2,070
2
votes
0
answers
94
views
Finding Hamilton cycles in random graphs
For a random graph $G$ of minimum degree 3, can we find a Hamilton cycle in linear time (with high probability for every edge density)?
If this is an open problem, I will also accept an empirically ...
- 2,537
2
votes
1
answer
181
views
Do reasonably competitive 3SAT algorithms ever have shrinking run-time distributions when measured as a probability density function?
The algorithms I know for solving 3SAT typically have exponential run-time distributions which become wider in their PDF as the number of variables, $N$, increases. For the exponential distribution ...
- 101
2
votes
0
answers
95
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 ...
- 2,070
2
votes
0
answers
181
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
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,681
2
votes
0
answers
165
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
2
votes
0
answers
171
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
2
votes
0
answers
107
views
$k$-XOR collision free families
Given parameters $n,k\in \mathbb N^+$, I'm interested in finding a set of binary vectors $V_{n,k}=\{v_1,\ldots,v_n\}$ of length that satisfies:
$\forall i: v_i\in\{0,1\}^{z_{n,k}}$.
The bitwise xor ...
- 9,438
2
votes
0
answers
72
views
Can we always find a graph with a given algebraic connectivity?
This is crossposted from math stackexchange. This is my first time posting here, so let me know if I'm doing something wrong.
I would like to experiment with various spectral properties of graphs, ...
- 121