Questions tagged [ds.algorithms]
Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.
260
questions
13
votes
1
answer
850
views
Largest common subgraph of two maximal planar graphs
Consider the following problem -
Given maximal planar graphs $G_1$ and $G_2$, find the graph $G$ with maximum number of edges such that there is a subgraph (not necessarily induced) in both $G_1$ and ...
- 1,631
13
votes
1
answer
442
views
Minimal elements of a monotonic predicate over the powerset $2^{|n|}$
Consider a monotonic predicate $P$ over the powerset $2^{|n|}$ (ordered by inclusion). By "monotonic" I mean: $\forall x, y \in 2^{|n|}$ such that $x \subset y$, if $P(x)$ then $P(y)$. I am looking ...
- 9,269
13
votes
0
answers
1k
views
What is the currently best known algorithm for the transportation problem?
Consider the well known transportation problem:
There are $m$ supply nodes, $n$ demand nodes and $k$ feasible arcs.
Every node has a integer supply or demand, and the arcs have integer costs, used ...
- 990
13
votes
5
answers
7k
views
Is there any gradient descent based technique for searching absolute minimum (maximum) of a function in multidimensional space?
I'm familiar with gradient descent algorithm which can find local minimum (maximum) of a given function.
Is there any modification of gradient descent which allows to find absolute minimum (maximum),...
- 233
13
votes
2
answers
585
views
Decentralized algorithm for determining influential nodes in social networks
In this paper by Kempe-Kleinberg-Tardos, the Authors propose a greedy algorithms based on submodular functions to determine the $k$ most influential nodes in a graph, with applications to social ...
- 203
13
votes
1
answer
977
views
Space-time tradeoff lower bounds
Following the discussion on lower bounds for 3SAT [1], I'm wondering what are the main lower bound results formulated as space-time tradeoffs. I'm excluding results such as, say, Savitch's theorem; a ...
13
votes
1
answer
556
views
Given a graph, decide if its edge connectivity is at least n/2 or not
Chapter 1 of the book The Probabilistic Method, by Alon and Spencer mentions the following problem:
Given a graph $G$, decide if its edge connectivity is at least $n/2$ or not.
The author mentions ...
- 1,631
13
votes
1
answer
993
views
Exact algorithms for non-convex quadratic programming
This question is about quadratic programming problems with box constraints (box-QP), i.e., optimisation problems of the form
minimise $f(\mathbf{x}) = \mathbf{x}^T A \mathbf{x} + \mathbf{c}^T \mathbf{...
- 11.5k
12
votes
0
answers
278
views
Conditional density of primes
We have some theorems about the density of prime numbers, the most famous one is probably the prime number theorem.
My question is
about the density of primes when we choose random numbers from a ...
- 21.6k
12
votes
1
answer
1k
views
What is the hardest instance for the group isomorphism problem?
Two groups $(G,\cdot)$ and $(H, \times)$ are said to be isomorphic iff there exists a homomorphism from $G$ to $H$ which is bijective. The group isomorphism problem is as follows: given two groups, ...
- 177
12
votes
3
answers
2k
views
counting independent sets
What algorithms/mathematical techniques are available to exactly/approximately count number of independent sets?
Is/Are there a good reference/good references on this topic?
I am interested in ...
- 2,208
12
votes
1
answer
600
views
Positive topological ordering, take 2
This is a followup to David Eppstein's recent question and is motivated by the same problems.
Suppose I have a dag with real-number weights on its vertices. Initially, all of the vertices are ...
- 23.1k
12
votes
2
answers
31k
views
Intuitively, why is the complementary slackness condition true?
What's an intuitive proof that shows that the conditions of complementary slackness are indeed true:
If $x^*_j > 0$ then the $j$-th constraint in the dual is binding.
If the $j$-th constraint in ...
- 5,305
12
votes
1
answer
519
views
Optimal randomized comparison sorting
So we all know the comparison-tree lower bound of $\lceil\log_2 n!\rceil$ on the worst-case number of comparisons made by a (deterministic) comparison sorting algorithm. It does not apply to ...
- 51k
12
votes
1
answer
1k
views
Optimal sort algorithm in number of swaps
Given a sequence of $n$ numbers, can it be sorted with $O(n \ln n)$ comparisons and $O(n)$ swaps/moves? Any pointer to publications on that matter or counterarguments showing a $\Omega(n \ln n)$ lower ...
- 123
12
votes
3
answers
480
views
Streaming derandomization
Stream algorithms require randomization for the most part to do anything nontrivial, and because of the small-space constraint, need PRGs that use little space. I know of two methods that have been ...
- 32.1k
12
votes
6
answers
2k
views
"Divide and conquer" data stream algorithms
What useful algorithms do there exist that work on huge data streams and also their results are fairly small and one can compute the result for a mixture of two streams by somehow merging their ...
- 8,951
12
votes
3
answers
800
views
A Multi-cut Problem
I'm looking for a name or any references to this problem.
Given a weighted graph $G = (V, E, w)$ find a partition of the vertices into up to $n = |V|$ sets $S_1,\ldots,S_n$ so as to maximize the ...
- 9,870
11
votes
4
answers
646
views
Lower bound for testing closeness in $L_2$ norm?
I was wondering if there was any lower bound (in terms of sample complexity) known for the following problem:
Given sample oracle access to two unknown distributions $D_1$, $D_2$ on $\{1,\dots,n\}$, ...
- 4,461
11
votes
1
answer
898
views
“Overflow” in Extended Euclidean Algorithm
Sorry if I'm mistaken with the place to ask the question (maybe I should go to stackoverflow.com/mathoverflow.net?).
I wonder if there is a proof that when evaluating extended Euclidean algorithm the ...
- 1,103
11
votes
3
answers
348
views
Computing distances with approximation less than 2 in general graphs?
Given a weighted undirected graph with $m = o(n^2)$ edges, I would like to compute distances of approximation less than 2 between any given pair of vertices. Of course, I would like to use ...
- 111
11
votes
2
answers
835
views
Are quasi-polynomial sized circuits for 3-SAT trivial?
Suppose we consider 3-SAT with $v$ variables and $c$ clauses. I am researching a method that appears to take $O(v^{2+\log c})$ time/space to solve any SAT problem fitting this description, to within ...
- 2,100
11
votes
3
answers
327
views
Bounds on approximating frequency moments
Let $a_1, a_2,\dotsc, a_m$ be a sequence of integers where each $a_j \in \{1,2,\dotsc,n\}$. For $i \in \{1,2,\dotsc,n\}$, let $m_i = |\{j : a_j = i\}|$. The $k$th frequency moment is defined to be
$\...
- 779
11
votes
2
answers
4k
views
Complexity of Finding the Eigendecomposition of a *Symmetric* Matrix
This is a specialized version of a previous question:
Complexity of Finding the Eigendecomposition of a Matrix .
For NxN symmetric matrices, it is known that O(N^3) time suffices to compute the ...
- 111
11
votes
1
answer
864
views
Finding a dual of a graph
According to the book Topological Graph Theory by Gross and Tucker, given a cellular embedding of a graph on a surface (by 'surface' I mean here a sphere with some $n\geq 0$ handles, and below $S_n$ ...
- 669
11
votes
1
answer
452
views
Computation of max H-free sets
In a graph, an independent set is a vertex subset which doesn't contain an edge as an induced subgraph. The problem of finding largest independent sets in a graph is a fundamental algorithmic question,...
- 1,952
11
votes
1
answer
414
views
Making SAT solvers competitive with specialized algorithms
What are obstacles to making SAT solvers competitive with specialized graph algorithms? In other words, is it feasible to expect SAT solvers that can replace the role of algorithm designer -- ie, be ...
- 4,701
11
votes
2
answers
573
views
Boolean formula balancing in $\mathsf{AC^0}$
I am looking for references about the complexity of Boolean formula balancing problem. In particular,
Was it known that Boolean formulas can be balanced in $\mathsf{AC^0}$?
Is there a simple proof of ...
- 21.6k
11
votes
1
answer
476
views
Constructing vectors in general position
Let a real $k\times n$ ($k\le n$) matrix ${\bf A}$ with the property that any collection of $k$ columns is full rank.
Q: Is there an efficient way to deterministically find a vector ${\bf a}$ such ...
- 1,356
10
votes
1
answer
1k
views
Algorithm to determine function equality on the simply typed lambda calculus?
We know that beta-equality of simply typed lambda-terms is decidable. Given M,N:σ→τ, is it decidable whether for all X:σ, MX $≃_β$ NX?
- 3,137
10
votes
5
answers
4k
views
Automata Theory / Formal Language Thesis Topic
Hey All,
I'm currently trying to find a solid masters thesis topic pertaining to some branch of automata theory or related to formal languages. I'm trying to generate some good ideas for what an ...
- 935
10
votes
3
answers
1k
views
Tree decomposition for planar graphs
First asked on math.SE with no replies.
Suppose I have a planar graph, with a planar embedding, how do I find tree decomposition?
What is the optimal tree decomposition of a $d$-by-$d$ square grid? ...
- 4,701
10
votes
1
answer
365
views
Can we construct a k-wise independent permutation on [n] using only constant time and space?
Let $k>0$ be a fixed constant.
Given an integer $n$, we want to construct a permutation $\sigma \in S_n$ such that:
The construction uses constant time and space (i.e. preprocessing takes constant ...
- 9,626
10
votes
8
answers
893
views
Is there any other algorithm whose worst-case running time is exponential meanwhile it works very well in practice other than Simplex Algorithm?
We generally call an algorithm "good algorithm" if it's runnning time is polynomial in the worst-case.
But in some cases (for example Simplex algorithm), eventhough the worst-case of the algorithm is ...
- 934
10
votes
1
answer
262
views
Is it decidable whether the output length of a transducer is bounded by the input length?
The transducers considered here are those Wikipedia calls finite state transducers. The behavior of a transducer $T$, that is, the relation it computes, is written $[T]$: a word $y$ is an output for $...
- 11k
9
votes
1
answer
478
views
Does There exist a particular PSPACE Complete Problem which has a FPTAS algorithm?
It is well known that the NP-Complete Problem called Subset Sum has a FPTAS. I was wondering if there existed an PSPACE Complete problem which also has a FPTAS? Thanks in advance.
- 1,578
9
votes
2
answers
7k
views
Time complexity of Held-Karp algorithm for TSP
When I looked through "A Dynamic Programming Approach to Sequencing Problems" by Michael Held and Richard M. Karp1, I came up with the following question:
why the complexity of their ...
- 4,215
9
votes
1
answer
1k
views
Powerful algorithms that are just too hard to implement-- how to be sure they are right?
I am referring to the question here: powerful algorithms too complex to implement.
If an algorithm is powerful, but too complex to implement, how can you be sure that the algorithm is correct? ...
- 409
9
votes
0
answers
308
views
Additive error in counting the number of 1's in a sliding window?
The setting is as follows:
We're given a stream of bits. At time $t$ you get to see bit $b_t$, and required to output $\widehat{s_t} \approx \Sigma_{i=0}^{N}b_{t-i}$ (i.e. approximately how many 1's ...
- 9,448
9
votes
3
answers
908
views
Non-Orthogonal Vectors Problem
Consider the following problems:
Orthogonal Vectors Problem
Input: A set $S$ of $n$ Boolean vectors each of length $d$.
Question: Do there exist distinct vectors $v_1$ and $v_2 \in S$ ...
- 5,127
8
votes
2
answers
1k
views
SDP relaxation of independent set
I'm looking at page 28 of Lovasz "Semidefinite programs and combinatorial optimization" and it gives the following approximation of independence number of the graph
$$\max u' Z u$$
subject to
$$Z\...
- 4,701
8
votes
2
answers
840
views
What is the initialization time of a link-cut tree?
Link-cut tree is a data structure invented by Sleator and Tarjan, which supports various operations and queries on a $n$-node forest in time $O(\log n)$. (For example, operation link combines two ...
- 7,648
8
votes
3
answers
1k
views
Determining connectivity for a fully dynamic graph with vertex/subgraph insertion and deletion
I am looking for a solution to the following problem and wonder if anyone could point me to some existing research on this topic. I am coming from a real world application of graph so bear with me if ...
8
votes
2
answers
1k
views
Approximation algorithms for MAX-CUT, when sizes of partition sets are fixed
The MAX-CUT problem has constant factor approximation, but we can't control the sizes of the sets in resulting partition. What is known about maximizing cut size, if we restrict one part of the ...
- 1,468
7
votes
1
answer
784
views
Approximating transitive reduction of a transitive closure of a dag
Let's suppose a transitive closure $G^+$ of a dag $G$ is given and we want to compute an approximation of the transitive reduction $G^-$ such that the full transitive reduction is a subgraph of the ...
- 696
7
votes
1
answer
273
views
Algorithm to find a polyhedral embedding
A polyhedral embedding of a graph on a surface is an embedding without edge crossings such that all the faces are bounded by simple cycles, and any two faces share a common vertex, share a common edge,...
- 669
7
votes
2
answers
455
views
What are the current best upper bounds of #P?
#P is the class of counting problems for problems in NP. In other words, a solution to #P returns the number of solutions to a particular problem in NP.
I'm wondering if there have been any studies ...
- 2,100
7
votes
4
answers
3k
views
What are the most effective algorithms to find random number?
I was reading the Ramsey's Theory stating "complete disorder is impossible". Is there any algorithm to generate random numbers for a long period of time without there being any relation from one set ...
- 181
7
votes
1
answer
1k
views
Reservoir sampling of distinct values
I'm faced with a situation where I need to get m samples from a data stream (without replacement). Only one pass through the data is possible.
In my case, the stream contains many duplicate values, ...
- 509
7
votes
2
answers
360
views
Testing boolean vectors orthogonality with fast query-time
Consider the following problems,
Problem1:
INPUT: a set $S:=\{s_1, \ldots, s_n\}$ of vectors in $d$-dimensional boolean vector space $\{0,1\}^d$ over $\mathbb{F}_2$
TASK: preprocess INPUT in such a ...
- 650