Newest Questions
50,066 questions
1
vote
0
answers
22
views
Sparse Kaczmarz with inequalities
Input:
A system of equalities of the form $Ax = b$
A system of inequalities of the form $Ax \le b$
where $x$ is subject to a sparsity objective using a minimized L1-norm.
Output:
$x$ such that its ...
0
votes
1
answer
14
views
$$\text{If } B \in \mathsf{SPACE}(\log^2 n) \text{ and } A \le_{\mathrm{L}} B, \text{ then } A \in \mathsf{SPACE}(\log^2 n)?$$
I am investigating the closure properties of specific space complexity classes. I am trying to determine the truth value of the following statement:
$$\text{If } B \in \mathsf{SPACE}(\log^2 n) \text{ ...
- 387
0
votes
0
answers
29
views
Show that CFG are closed under reversal using a NPDA
I need to show that NPDA (Non deterministic pushdown automata) are closed under reversal.
My idea was to add a new starting state that pushes the entire input on the stack since there it is in the non-...
- 1
0
votes
1
answer
17
views
Subtree of Another Tree Complexity: Alternative Solution Analysis
To find out if a tree is a subtree of another, there is an O(m*n) complexity solution that I'm aware of, that looks a bit like:
...
0
votes
0
answers
5
views
Is “provisioning” the right term in an M.Sc. thesis title on tool abstraction for distributed compute infrastructures?
I am about to submit my M.Sc. thesis and would appreciate advice on the wording of the thesis title.
Context
In many distributed and heterogeneous compute environments (e.g., Slurm-based HPC clusters ...
- 101
0
votes
0
answers
21
views
Lower bound design for Branch and Bound in the Minimum Difference Partitioning problem
I am studying the Minimum Difference Partitioning problem:
Given a set of positive integers with total sum, partition the set into two subsets such that the absolute difference between the sums of ...
- 1,954
0
votes
1
answer
42
views
Is it really possible to solve triangle point inclusion problem with angles?
Given an input of 4 list of coordinates, last three lists are describing three vertices of a triangle, first list describes point O. using this input you have to determine if point O is in the ...
0
votes
1
answer
16
views
What does "one step" in a local search really mean?
I'm having trouble understanding what one step in a local search really means.
In the course I'm taking, there was this old exam question: "Describe what happens in one step in a local search ...
- 33
0
votes
0
answers
18
views
Why is x bounded with type nat?
I am doing an excercise in the book Type Theory and Formal Proofs. In 3.31 a, we are provided with a definition of natural number addition:
$$
\text{add} \equiv \lambda m, n : \texttt{nat}. \lambda \...
2
votes
2
answers
197
views
Odd cycle through a given edge
Given an undirected graph $G$ and an edge $e$, I want to know if there is an odd cycle that goes through $e$.
Does an algorithm exist that solves such a problem in polynomial time?
0
votes
0
answers
18
views
In Skiena’s Psychic Modeling example, why is 𝑗 included in the initial model when only 𝑙-subsets are explicitly covered?
I am reading Section 1.8 (“War Story: Psychic Modeling”) from Skiena’s The Algorithm Design Manual and am confused about the role and interpretation of the parameter 𝑗 in the initial (nave) set-cover ...
- 11
2
votes
0
answers
31
views
What's the best way to find most optimal packing problem solutions?
I would like to use machine learning or some kind of algorithm to find optimal solutions to the 2D packing problem (the arrangement of N unit shapes into another shape that results in the smallest ...
- 121
1
vote
1
answer
44
views
Confusing statement about “even-length chain” in Skiena's Algorithm Design Manual
I’m reading Skiena's Algorithm Design Manual 3rd edition, specifically the “Stop and Think: Greedy Movie Stars?” counterexample (Figure 1.7).
The greedy heuristic considered is:
repeatedly pick the ...
- 11
1
vote
2
answers
69
views
Counting monotone sequences with strictly increasing XOR differences
I would like to understand the structure of sequences whose consecutive XOR values increase strictly. The problem is as follows.
Let integers $(l,r)$ be given with $1\le l\le r$.
Consider all finite ...
- 11
1
vote
0
answers
54
views
Are all known NP-complete problems known to be p-isomorphic?
I am currently looking into Berman-Hartmanis Conjecture. [Paper 1, Wiki]
In the abstract of Paper 1, it is mentioned that all the known problems are p-isomorphic. (Paper was published in 1975.) The ...
- 219
