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
8
votes
0
answers
199
views
Complexity of checking if AB intersects C
Let $A,B,C$ be subsets of a nonabelian group $G$,
and assume we know the structure of $G$ "fairly well"
(e.g., $G = S_n$ or $A_n$).
Assume that group operations take $O(1)$ time.
Is it ...
- 3,243
8
votes
0
answers
487
views
Nuts and Bolts problem: Simpler $o(n^2)$ algorithm
In this paper, the authors mention that it is possible to get an $o(n^2)$-time algorithm for the nuts and bolts problem by choosing samples based on a projective plane. They also mention that a non-...
- 401
8
votes
0
answers
342
views
Combinatorial method for computing the largest eigenvector of the adjacency matrix of a graph
Given a connected and non-bipartite graph $G=(V,E)$ with vertex set $V=\{1,\cdots, n\}$, let $A$ denote its adjacency matrix and let $deg(i)$ denote the degree of vertex $i$. Let $D$ be a diagonal ...
8
votes
0
answers
177
views
Is the dominating set problem constant-factor-approximable in undirected path graphs?
I am interested in the complexity of the minimum dominating set problem (MDSP) in some specific graph class.
A graph is an undirected path graph if it is the vertex-intersection graph of a family of ...
- 2,143
8
votes
0
answers
366
views
Efficiently approximating derivative of a well-behaved function
I need an algorithm for adaptive sampling a well-behaved function and computing its derivative in the sampling range with prescribed accuracy. The function has no more than one minimum in the sampling ...
- 189
8
votes
0
answers
171
views
Can one find good distance-2-separators in planar graphs?
It is known that planar graphs admit "good" separators, allowing to design PTASes for specific problems such as MINIMUM INDEPENDENT SET by recursive separation of the graph.
However, it ...
- 2,143
8
votes
0
answers
195
views
what is the best heuristic to solve 3AP with Euclidean costs?
As is well known, assignment problems for $n$-partite graphs, with $n$>2 are NP-hard, where as assignment problems on bipartite graphs can be solved in polynomial time using the Kuhn's Hungarian ...
- 81
8
votes
0
answers
113
views
Efficient Enumeration and Parameterization of Graphs Deriving from Delaunay Tesselations in 3D
This is a repost from a question on Computational Science. No proper answer was found and it was suggested that TCS might be able to answer. So here it goes:
Is there an algorithm that enumerates the ...
- 191
8
votes
0
answers
2k
views
Fast Hamiltonian Cycle finding Algorithm
We are struggling to understand a fast algorithm for finding Hamiltonian cycle (for random graphs) due to Prof. Alan Frieze* and see whether that algorithm could be implemented efficiently. If there ...
msk
8
votes
0
answers
438
views
Type inference with subtype constraints and polymorphism using Trifonov and Smith's constraint maps
Trifonov and Smith's Subtyping Constrained Types (1996) introduces constraint maps to represent consistent closed constraint sets (such maps providing sets of lower and upper bounds to each variable ...
- 1,379
7
votes
0
answers
168
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 ...
- 193
7
votes
0
answers
192
views
Tortoise and hare algorithms
Consider the problem:
Given an array $a[0..n]$ where $n\ge 1$ and $a[i]\in [n]$ for all $i=0,\ldots,n$ find two indices $s\neq t$ so that $a[s] = a[t]$.
This problem has a stunning solution running ...
- 173
7
votes
0
answers
114
views
Consequence of Decision Tree Complexity of $k$-SUM Problem
Ezra and Sharir showed the $O(n^2\log^2 n)$ linear decision tree complexity for $k$-SUM problem [1], which improves the $O(n^3\log^3 n)$ complexity result of Cardinal et al [2].
It is known that $k$-...
user17918
7
votes
0
answers
466
views
Worst-case computational complexity of solving Diophantine equation
Manders and Adleman proved that the following decision problem is NP-complete:
Given integers $a,b,c>0$, does the quadratic equation $ax^2+by-c=0$ have a solution in integers $x,y>0$?
The ...
- 793
7
votes
0
answers
266
views
Positive cut algorithm on bipartite graphs with negative weights
Let $G=(V,E,w)$ be a bipartite graph with weight function $w:E→\{-1,1\}$. Is there an efficient (polynomial) algorithm for finding some positive (not necessarily maximum) cut of $G$, if one exists? If ...
- 71
7
votes
0
answers
277
views
Integer queue summation
As part of a project I'm working on, we came up with an efficient algorithm for approximating the sum of an integers queue.
The setting is as follows: Let $\epsilon>0$. we need to maintain a space-...
- 9,438
7
votes
0
answers
1k
views
Is there a linear-time algorithm for max flow on dags
What is the fastest known algorithm for max flow on dags?
Can there be a linear-time algorithm running in time $O(|V|+|E|)$?
Input: a weighted dag $G=(V,E,w)$ where
$E$ is given as an edge list $E$ ...
- 171
7
votes
0
answers
68
views
Explicit error bounds on the abelian hidden subgroup problem
What are some explicit forms for the error probability in the typical quantum abelian hidden subgroup algorithm as a function of oracles queries?
Ettinger, Hoyer, and Knill give a result that the ...
- 91
7
votes
0
answers
1k
views
Best algorithm for inversion of symmetric positive-definite matrices
As I know, the time complexity for usual inversion algorithm of general matrix is $O(n^3)$. In recent years, there is a improvement from $O(n^3)$ to $O(n^{2.8....})$. However, does there exists a ...
- 171
7
votes
0
answers
225
views
Is there a programming language where any arbitrary recursive function can be fused?
Compilers like GHC for Haskell use inlining as one of its most important optimising tools. Doing that is not possible for recursive functions, in general. A few techniques have been developed to amend ...
- 3,117
7
votes
0
answers
374
views
Minimum length cuts needed to remove holes in a polygon
Suppose I'm given a connected polygon in the plane with holes. I can "remove" a hole by drawing a straight line from the boundary of a hole to another boundary (either of another hole, or the boundary ...
- 32k
7
votes
0
answers
205
views
Is the following "Occam's razor" decision problem a member of P?
While thinking about natural language processing, I came up with the following NP problem:
OCCAM-k: Given a fixed natural number $k$, consider the following input: a natural number of states $S$ in ...
user1338
7
votes
0
answers
120
views
Is there any known result for 1-median problem with negative weights in Euclidean space?
Given a set of $n$ points $v_1,\ldots,v_n$ in $R^d$, find a point $p$
such that $\sum_{i=1}^n w_i d(p,v_i)$ is minimized, where $w_i$ is the
weight of $v_i$, which may be positive or negative.
...
- 769
7
votes
0
answers
155
views
Lower bound for the maximal vectors problem
I am studying the (worst-case) complexity $C(n,d)$ required to solve the maximal vector problem: given a finite set $V$ of $n$ $d$-dimensional vectors, compute the set of undominated (a.k.a. skyline, ...
- 1,085
7
votes
0
answers
3k
views
Time complexity of standard semidefinite programming solvers
I am interested in exact scaling of the ellipsoid method and interior point methods for solving SDPs.
(I am not interested in algorithms like multiplicative weights updates method.)
- 121
7
votes
0
answers
963
views
Biconnected components of a directed graph?
I am looking for an algorithm for computing the biconnected components of a strongly connected directed graph.
- 481
7
votes
0
answers
496
views
An algorithm to compute the number of paths of length at most k
So I had to answer the following question:
Given a graph $G = (V, E)$, and two vertices $v_i, v_j$, compute the number of walks between $v_i$ and $v_j$ of length at most $k$. $G$ is not too large, ...
- 445
7
votes
0
answers
230
views
Minimum weight expander
Expander constructions given an expander which is a sub-graph of a complete graph. Sometimes we don't want to construct an arbitrary expander, want to find an expander inside another given graph. In a ...
- 4,001
7
votes
0
answers
250
views
How quickly can we find an arbitrary digit in multiplication?
In considering an answer to this question, I once again wondered how quickly we could find a digit in multiplication.
We may first consider previous results. Finding the least significant digits is ...
- 2,100
7
votes
0
answers
189
views
Testing the degree of a vertex
Let's say we have a graph $G$ with $n$ vertices. Given $\epsilon>0$ and a specific vertex $v$, consider the problem of deciding whether $\mathrm{deg}(v) < \frac{\epsilon}{3}n$ or $\mathrm{deg}(v)...
- 725
7
votes
0
answers
199
views
Tree search guided by a probabilistic oracle
I'm trying to find a solution for the following problem.
I have a tree $T$ of branching factor $b$ and depth $d$. For the moment, I only care about the case where I restrict $b=2$, but I would be ...
- 249
7
votes
0
answers
239
views
Can we achieve a better kernel for the Vertex Cover problem on planar graphs?
We have known how to get a $2k$ kernel for the Vertex Cover problem for thirty years, and it is not expected to be improved assuming UGC.
My question is, can we do better for planar graphs? It is easy ...
- 2,560
7
votes
0
answers
1k
views
Sparse graphs versus dense graphs
I am curious if there are graphs problems for which either -
we know that time and/or space complexity is independent of graph sparsity
we do not know whether or not graph sparsity can be exploited ...
- 838
7
votes
0
answers
831
views
Approximation results for 3-partition
The 3-partition as defined here is a strongly NP-complete decision problem. Consider one optimization problem of 3-partition where the $m$ subsets each have at most three elements and a sum of not ...
- 951
7
votes
0
answers
191
views
Scaling Algorithms for the Minimum Spanning Tree Problem?
In his paper "Scaling Algorithms for Network Problems", Harold Gabow details several algorithms for graph problems that work using scaling, iteratively refining a candidate answer by beginning with a ...
- 2,121
7
votes
0
answers
100
views
Ref - Implicit selection made quick?
Given a matrix of size $n\times n$ with numbers, where every row is sorted, one can compute the $k$th smallest element in $O(n \log^2 n)$ time by simulating (implicitly) quick-select on this matrix (...
- 9,596
7
votes
0
answers
160
views
log(OPT) approximation for directed balanced vertex separator
Leighton, Rao presented an $O(\log n)$ approximation algorithm for directed and undirected balanced vertex separator. Agarwal, Charikar, Makarychev, Makarychev improved this approximation factor of ...
- 1,953
7
votes
0
answers
353
views
Good MCMC methods for exploring the space of independent sets
Let $G$ be an edge-weighted graph, and let (S, V-S) be a feasible pair if S is a maximal independent set. The weight of a feasible pair is computed by finding for each element of V-S the lightest edge ...
- 32k
7
votes
0
answers
392
views
Embedded dynamic programming (and planar subgraph isomorphism)
In Planar Subgraph Isomorphism Revisited, Frederic Dorn obtains an improved algorithm for Planar Subgraph Isomorphism, by using a technique he calls Embedded Dynamic Programming. This technique ...
- 6,994
7
votes
0
answers
166
views
Finding the set of paths of smallest cumulated length that cover a given set of patterns
First of all, sorry for this long and maybe not very informative title...
Context:
Let $G=(V,E)$ be a directed graph, let $v_0 \in V$ be the initial node of paths that I will consider in the graph.
...
- 3,063
6
votes
0
answers
165
views
Computing and maintaining the minimum of a set $S$ of integers while allowing updates on $S$
This question is about computing and maintaining the minimum of a set $S$ of integers while allowing updates on $S$.
The computation model we are considering is the unit-cost RAM machine with linear ...
- 775
6
votes
0
answers
198
views
Bottleneck $k$-link path in a complete DAG
Let $G$ be a complete DAG: It has vertices $v_1,\ldots,v_n$, and $v_iv_j$ is an edge if and only if $i<j$.
Let $w(i,j)$ be the weight of the edge $v_iv_j$. The weight has the property that $w(i,j)&...
- 4,367
6
votes
0
answers
138
views
Evaluating addition chains
I hope this is a suitable place to ask this question.
An addition chain of size $n$ is a sequence $x_1, \dots, x_n$, where $x_1$ is fixed to 1 and $x_i = x_j + x_k$ for some $j,k < i$. I am ...
- 161
6
votes
0
answers
169
views
Machine learning algorithms on hypergrap models
Graphical models are a very useful tool with many applications,
whereby a joint distribution of a set of random variables is modeled
using only pairwise dependencies between the variables, and
two ...
- 359
6
votes
0
answers
118
views
Lower bounds for randomized frequency estimation algorithms
Consider a stream of elements $s_1s_2\ldots s_N$.
A counter-based frequency estimation algorithm uses $m$ counters and is required to answer queries of the form "How many times did $x$ appear"?
It ...
- 9,438
6
votes
0
answers
148
views
Is higher-order unification decidable for terms without abstractions within applications?
Consider the problem of higher order unification - that is, finding a substitution for the equation a = b, where a and ...
- 3,117
6
votes
0
answers
182
views
Statistical Algorithms vs Convex Relaxations - Planted Clique
I am trying to understand exactly what the lower bounds for the query complexity of statistical algorithms imply for convex relaxations for the planted clique problem ?
A recent paper by Feldman, ...
- 666
6
votes
0
answers
96
views
Perfect hashing family variation - injectivity on $r$ disjoint sets
We denote by $[t]$ the set $\{1,2,\ldots,t\}$.
A $(n,k)$-perfect hashing family is a set of functions $H=\{h_i:[n]\to[k]\}$ such that for every set $S\subset [n], |S|\leq k$, there exists some $h_S \...
- 9,438
6
votes
0
answers
692
views
Generalized sequential machine synthesis subject to language equivalence/inclusion and reachability
A generalized sequential machine (GSM) is a generalization of a Mealy machine where on each transition one input symbol is read and 0 or more output symbols are written. As in a Mealy machine, we ...
- 61
6
votes
0
answers
400
views
Bipartite vertex separator
Are there any common approaches for finding a vertex separator in a bipartite graph $G = (V_1, V_2, E)$ where the selected vertices are constrained to come from one partition of the graph?
I have a ...
- 211