Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.
1
vote
0answers
84 views
The number of maximal subsets with sum less than $m$
I've met this problem.
I would like to know to which complexity class it belongs.
Input
a set of positive integers $I$,
an integer $m$,
an integer $n$.
Question
Is the number of $S \subseteq I$ ...
1
vote
1answer
41 views
bounds in centralized and distributed
If we know some lower bound of the solution of a problem in centralized setting, what can we say about the lower bound in a distributed setting?
-3
votes
0answers
31 views
how to prove this unsolvable problem about halting problem (turing machine) [migrated]
Show that the problem of deciding, for a given TM M, whether M halts for all inputs within n^2(namely n square ) steps(n is the length of the input) is unsolvable. You can use the fact without proof ...
-1
votes
0answers
30 views
Why does Shellsort work well on Sorted and Reverse ordered lists? [migrated]
I've ran some tests and found that Shellsort runs much faster on ordered and reversed lists compared to random lists and almost ordered lists.
...
2
votes
0answers
45 views
Determination of maximum number of incoming transitions to a state in any trace-equivalent representation of an LTS
Suppose $L$ is a labelled transition system (LTS). Suppose that the function $maxIn(L)$ (LTS $\rightarrow$ integer) returns the number of incoming transitions to the state of $L$ that has the most ...
-4
votes
0answers
72 views
The sum of all integers less than n with a zero [migrated]
For example, if n=14, the output should be 10; n=22, the output should be 30=10+20; n=102, output=(10+...+100)+101+102=5703
In this problem, n is smaller than $10^{18}$ , and the algorithm should ...
-1
votes
0answers
90 views
Graph Has Two / Three Different Minimal Spanning Trees? [closed]
I'm trying to find an efficient method of detecting whether a given graph G has two different minimal spanning trees. I'm also trying to find a method to check whether it has 3 different minimal ...
-1
votes
0answers
36 views
Bound on vertex heights in Push-Relabel
I'm having a little bit of trouble understanding Lemma 26.20 in CLRS 3rd Edition. It states that on a graph $G=(V,E)$, $\forall v \in V, h(v) \leq 2|V| - 1$. I can see the intuition behind the proof, ...
6
votes
0answers
151 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, ...
-6
votes
0answers
73 views
Show that it is undecidable if two TMs accept the same language [closed]
I was asked this question at an interview, and couldn't answer it, and would like to know how it is 'shown'. This is NOT HW!
4
votes
0answers
42 views
Find index set partition that has large projections
I have a multiset $S$ of $n$-bit strings. Let $1_S(s)$ denote the number of times that string $s$ appears in $S$, i.e., the multiplicity of $s$ in $S$. I want to find a partition of ...
-3
votes
0answers
53 views
How many Trees are Possible? [closed]
We are given Two Integers P and Q.
We have to find how many different T-Trees are possible.
Definition of T-Tree
It is a tree with Q * P Nodes. Nodes are Numbered from 0 to Q * P - 1
The Nodes a ...
-2
votes
0answers
47 views
Finding the lower bounds of an algorithm [closed]
I am struggling to calculate the lower bounds of an algorithm. What is the right way to proceed.
For eg, I have the following algorithm
...
4
votes
1answer
101 views
A generalization of the geometric closest pair problem to balls
In one version of the classical closest pair problem, one is given a set $S \subseteq \mathbb{R}^2$ and asked to find distinct $x, y \in S$ such that $\|x - y\|$ is minimized for some norm $\| \cdot ...
-2
votes
0answers
62 views
A simple distinguisher question [closed]
I am given an oracle $A$ that takes input samples from two distributions $\chi_1$ and $\chi_2$.
Suppose we have $Pr_{x \sim \chi_1}[A(x) = 1] = p_1$ and $Pr_{x \sim \chi_2}[A(x) = 1] = p_2$, where ...
2
votes
1answer
141 views
Finding the shortest path in the presence of negative cycles
Given a directed cyclic graph where the weight of each edge may be negative the concept of a "shortest path" only makes sense if there are no negative cycles, and in that case you can apply the ...
-1
votes
0answers
39 views
Is there a general way to convert a critical section to one or more semaphores? [migrated]
Is there a general way to convert a critical section to one or more semaphores? That is, is there some sort of straightforward transformation of the code that can be done to convert them?
For ...
-2
votes
0answers
55 views
Finding average distance while travelling on an infinite wall [migrated]
Ok here is the question:
There is an infinite wall with a hole somewhere, you are placed on that wall at a random position. Let the distance between your initial position & hole be X. Find the ...
2
votes
1answer
165 views
Finding max of two elements in linear time with restriction
I have a matrix in the following form:
...
-4
votes
0answers
49 views
polynomial time [closed]
In both parts , provide an analysis of the time complexity of your algorithm
a- show that EQ dfa is in P.
B- Show that a language A is star-closed if A=A*.Give a polynomial time algorithm to test ...
4
votes
0answers
97 views
Fast algorithm for successively merging k-overlapping sets?
Consider the following algorithm for clustering sets: Begin with $n$ sets, $S_1, S_2, \ldots,S_n$, such that $$\sum_{i = 1}^n |S_i| = m \,,$$ and successively merge sets with at least $k$ elements in ...
-5
votes
0answers
80 views
Solving system of linear inequalities [migrated]
I am trying to solve a system of inequalities in the following form:
$\ x_i - x_j \leq w $
I know these inequalities can be solved using Bellman-Ford algorithm. ...
-2
votes
0answers
38 views
Algorithm for fastest filling of a field in a list with unused values from another list
I have:
PERSON which is a set of elements (about 1 million)
COUPONS which is a big set of elements (about 6 millions)
CODES which is a set of 9999 elements
With these rules
Every PERSON might ...
16
votes
4answers
508 views
How to obtain the unknown values $a_i,b_j$ given an unordered list of $a_i-b_j\mod N$?
Can anyone help me with the following problem?
I want to find some values $a_i,b_j$ (mod $N$) where $i=1,2,…,K, j=1,2,…,K $ (for example $K=6$), given a list of $K^2$ values that correspond to the ...
1
vote
0answers
69 views
Poly-time Algorithm for Non-Linear Optimization
As we know, linear programming is one of the most basic area of optimization theory, and computing an optimal solution can be excuted within poly-time. My question is about an extention of this ...
9
votes
1answer
178 views
Heapsort:Heaps =~ Quicksort:BSTs =~ Mergesort:___?
Please excuse the terseness of the title, I may have sacrificed clarity on the altar of conciseness.
One can see that inserting elements of an array into a binary search tree and reading them back ...
11
votes
2answers
584 views
Small graph with gap between chromatic and vector chromatic number?
I’m looking for a small graph $G$ whose vector chromatic number is smaller than the chromatic number, $\chi_v(G)<\chi(G)$.
($G$ has vector chromatic number $q$ if there is an assignment $x\colon V ...
2
votes
1answer
80 views
Verifying consistency of strict and non-strict partial orders constraints
I am building a set of constraints of the kind $x < y$ and $x \leq y$, where $<$ is a strict order and $\leq$ is a non-strict order on the same set, and $x$ and $y$ are abstract variables ...
3
votes
1answer
114 views
What is the fastest deterministic algorithm for incremental dynamic tree reachability?
As the title. The dynamic algorithm maintains the transitive closure of a tree when the tree undergoes a series of edge insertions (but no deletions)? And the algorithm supports constant query time.
...
2
votes
0answers
57 views
General covering approximation
Consider the following integer program (general covering):
$\min c \cdot x$ subject to
$Ax \ge b$,
where all entries in $A, b, c$ are nonnegative and $x$ is required
to be nonnegative and integral.
...
7
votes
0answers
94 views
Simplifying the disjoint union of wildcard strings
Setting: patterns with "don't care" symbols, binary alphabet.
For example, pattern $x = 001?$ represents the set $L(x) = \{0010, 0011\}$.
We are given a set $P$ of disjoint patterns: $L(x) \cap L(y) ...
3
votes
2answers
159 views
Generalization of independent set
I know the definition of the independent set problem in graph theory. An independent set cannot contain any two adjacent vertices.
How about if you allow no more than $k$ pairs of adjacent vertices? ...
6
votes
3answers
556 views
The Drawing Challenge - a problem I made up and can't solve!
I made up the following problem but have not made any headway in solving it in anything less than exponential time. Hopefully somebody can shed some light on it. I'm starting to think it may be ...
3
votes
1answer
155 views
A weighted sorting problem
Given a data matrix $D=[d_1 ... d_N]$, one would like to sort it in terms of rows such that the weighted distance of sorted $d$s to a target vector $y$ is being minimized.
It can be formulated as ...
2
votes
1answer
94 views
Computing unique subset intersections
Given a set S = {si : {zj : z ∈ N} }, what is a time-efficient algorithm for computing the unique sets of intersections of all of the subsets of S?
As per @JeffE's comment below, there are edge ...
1
vote
0answers
131 views
Dynamic shortest path data structure for DAG
Let $G$ be a dynamic DAG (directed acyclic graph) where new vertices and new edges can be inserted.
I am looking for an efficient data structure/algorithm to maintain the shortest path from a fixed ...
1
vote
0answers
102 views
What does “no integrality gap” implies?
I'm currently working on a linear time heuristic for the rectangle decomposition of binary matrix. This problem has a polynomial time solution, which in our case it too slow for large scale ...
0
votes
1answer
113 views
FPTAS for Number Partition Problem
I've been given a task to implement two algorithms (an exact algorithm and fully polynomial approximation scheme) for number partitioning problem. I found out that I can use some modification of ...
3
votes
2answers
141 views
Follow-the-leader algorithm in swarm formation: literature on the subject?
In an AI strategy game simulation, I devised an algorithm for forming a group and swarming a known location without communication among soldiers (ie. every individual agent makes a locally optimum ...
0
votes
0answers
56 views
Nonnegative Permanent and Ellipsoidal Method
Famously, Barahona gave an algorithm for Max Cut for Graphs without K5 complete as Subfactor Graph.
This was based on the Ellipsoidal Method.
Finding a Max Cut is the same for Bipartite Graphs as ...
9
votes
3answers
231 views
Find the remainder of a large fixed polynomial when divided by a small unknown polynomial
Assume we operate in a finite field. We are given a large fixed polynomial p(x) (of, say, degree 1000) over this field. This polynomial is known beforehand and we are allowed to do computation using a ...
5
votes
1answer
115 views
Canonical labeling of special classes of DAGs
Graph Isomorphism of directed acyclic graphs (DAGs) is known to be GI-complete. So a polynomial time algorithm to canonize DAGs is not known.
What are some special classes of DAGs that can be ...
4
votes
0answers
99 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 ...
1
vote
1answer
84 views
Max flow with conditional edges
Is anyone aware of a max flow algorithm where the edges are conditioned upon one another?
Meaning if I send f units of flow from vertex a --> b, then I have to send .5*f* unit from a --> c.
0
votes
1answer
212 views
Approximation algorithm for graph problem
In the process of trying to create an approximation algorithm for the following problem.
Let $G = (V,E)$ be a graph, $c_e, c_{iv} \ge 0$, for $e \in E$, $i \in L$, and $v \in V$, where $L$ is a ...
6
votes
0answers
75 views
Increasing the capacity to maximize the min cut
Consider a graph with all edges having unit capacity.
One can find the min cut in polynomial time.
Suppose I am allowed to increase the capacity of any $k$ edges to infinity
(equivalent to merging ...
15
votes
2answers
239 views
Bigger picture behind the choice of matrices in the Strassen algorithm
In the Strassen algorithm, to compute the product of two matrices $\mathbf{A}$ and $\mathbf{B}$, the matrices $\mathbf{A}$ and $\mathbf{B}$ are divided into $2 \times 2$ block matrices and the ...
8
votes
0answers
115 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 ...
7
votes
1answer
133 views
Approximation algorithms for Directed Minimum Cut with Cardinality Constraints
We would like to know whether there are any known approximation results for the cardinality constrained minimum $s$-$t$-cut on directed graphs. We weren't able to find any such result in literature.
...
2
votes
0answers
129 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 ...
