Questions tagged [algorithms]
Informally, an algorithm is a set of explicit instructions used to solve a problem (e.g. Euclid's algorithm for computing the greatest common divisor of two integers). For more specific questions on algorithms, this tag may be used in conjunction with the approximation-algorithms, algorithmic-randomness and algorithmic-topology tags.
1,561
questions
3
votes
1
answer
103
views
Is coprimality in $NC$?
Following reference https://pdfs.semanticscholar.org/e86e/8d7a267a29b9ad4ca112828109adfec55e8b.pdf claims integer coprimality is in $NC$ and it also has one citation. Is this claim valid?
3
votes
1
answer
186
views
Matching two sequences between each other
Given the sequence of symbols $A$ (contains ~10,000 symbols) and sequence of blocks $B$ (contains ~3,000 blocks, ~30 symbols inside each block) I need to exclude some blocks from sequence $B$ so that ...
3
votes
1
answer
2k
views
Transforming a non-invertible matrix into an invertible matrix
Given a non-invertible, diagonalizable matrix $A$, I wish to transform it into another matrix $B$ that satisfies:
$B$ is invertible
all non-zero eigenvalues of $A$, are also eigenvalues of $B$
all of ...
3
votes
1
answer
144
views
A modified bipartite assignment problem
Consider the following optimization problem. I have $n$ advisors and $dn$ students. I want to assign each student an advisor so that each advisor has exactly $d$ students. Each advisor/student pair ...
3
votes
2
answers
550
views
Bellman-Ford for Matching Problems?
I am looking for a simple way of calculating minimum-weight perfect matchings in complete graphs with an even number of vertices.
I know that there are implementations that are based on Edmond's ...
3
votes
1
answer
158
views
Parallel algorithm for modular multiplication of polynomials over Z/nZ
Is there a parallel algorithm for doing modular multiplication of polynomials over Z/nZ? n is a very large number (for hundreds and thousands of bits).
Normally, the method used is binary ...
3
votes
2
answers
427
views
Paper of Denis Simon on quadratic equations in dimensions 4, 5?
In several places I have come across references to a 2005-6 preprint of Denis Simon entitled
Quadratic equations in dimensions 4, 5, and more
This paper gives fast algorithms to find isotropic ...
3
votes
1
answer
303
views
Directed Hypercube Minimal Cuts
If $[n]:=\{1,2,\ldots, n\}$ for some $n\in\mathbb{N}$, then the hypercube digraph of dimension $n$, denoted $H_n$, is the graph whose set of vertices is the power-set $\wp([n])$ where two vertices $U,...
3
votes
1
answer
577
views
Sorting interleaved sorted lists
By interleaving two lists I mean to combine them into a single list in any way that maintains the relative order of the elements coming from each list. For example, interleaving $(x_1,x_2,x_3)$ and $(...
3
votes
2
answers
215
views
Equipartition of the circle [closed]
Browsing an old technical studies pupil's school book, I have found the description of a method to place at equal distance $N$ points on the circumference of a circle. I am looking for a proof of this ...
3
votes
2
answers
430
views
Geodesics in Graphs:Shortest Paths vs Going as Straight Ahead as Possible
According to Wikipedia http://en.wikipedia.org/wiki/Geodesic, a geodesic " is a generalization of the notion of a "straight line" to "curved spaces " and further " In the presence of an affine ...
3
votes
1
answer
209
views
Using Fourier Transform to speed up calculation of forces following an inverse square law
Suppose I have $n$ electric point charges in, say, two dimensions. Is there any algorithm (and I have a hunch that it might be related to the Fourier transform) to compute the net forces that act on ...
3
votes
1
answer
148
views
Search for common substructures in list of graphs
I have had the following problem on several occasions and I was wondering whether there is a general technique to solve this problem.
Given a list of graphs with property $P$. Is there a general ...
3
votes
1
answer
753
views
automating Math Overflow
Recently IBM Watson demonstrated the effectiveness of a natural language question answering algorithm. Of course, beyond the game of Jeopardy, this problem becomes more difficult. The accumulated ...
3
votes
1
answer
397
views
How "often" does LLL-reduction produce "optimal" result ? Is there condition (or informal understanding) on lattice that it LLL is optimal ?
Consider some lattice in R^4 (C^4) or C^8.
Famous "lattice reduction" procedures (like LLL latice reduction)
produces some "reduced basis". However in general there results are not "the best reduced"...
3
votes
1
answer
801
views
Algorithm for Ham Sandwich with Points
I just recently learned the Ham Sandwich Theorem in my algebraic topology class. If we take the measure to be the counting measure and let $n=2$, then the theorem tells us that given a set of black ...
3
votes
1
answer
1k
views
Is quadratic programming still NP-hard if you have bounds and a feasible point?
The reason I am wondering this is that all of the reductions from 3-SAT => quadratic programming (or similar NP-hard reductions) involve encoding the underlying NP-hard problem into feasibility ...
3
votes
3
answers
5k
views
Determining the space complexity of van Emde Boas trees
We call $S(u)$ the space complexity of the vEB tree holding elements in the range $0$ to $u-1$, and suppose without loss of generality that $u$ is of the form $2^{2^k}$.
It's easy to get the ...
3
votes
1
answer
179
views
Algorithm for finding a minimum weight circuit in a weighted binary matroid
For a given weighted graph $G = (V, E)$, there is a simple algorithm for finding the minimum weight circuit by running Dijkstra's algorithm $|E|$ times.
Also for a matroid $M = (E, I)$ one can use the ...
3
votes
1
answer
155
views
How to construct a lattice having a subset of a given relations?
I am given a (smallish, say $n=14$ element) set $X$, and a set $R$ of (a few hundred) quadruples of elements $(a, b, c, d)$ with $a,b,c, d\in X$.
I want to construct lattices on $X$, such that for all ...
3
votes
1
answer
73
views
Minimize player duplication in schedule
I am organizing quiz for the university and I am having some problems with creating good schedule for this.
The tournament format is as follows:
There are 6 * k players participating {k could be 7,8,...
3
votes
1
answer
242
views
Curious about an old algorithm which calculates modular inverse [closed]
I am not sure if I should ask this question here or somewhere else.
Background: I was searching through random mathematics paper that are related to cryptography and I came across this paper (page 3)....
3
votes
2
answers
183
views
Is there an algorithm for generating sets of routes that satisfy edge volume constraints?
I have reduced a problem I'm working on to something resembling a graph theory problem, and my limited intuition tells me that it's not so esoteric that only I could have ever considered it. I'm ...
3
votes
1
answer
328
views
What is the Complexity Class of the "Function Variant" of the Integer Factorization Problem?
I've been reading up a lot Prime Factorization and it's complexity, including a fair number of questions on this very site. However, I still feel there is a question still left unanswered.
So, ...
3
votes
2
answers
175
views
Sampling from maximally skewed stable distribution
I am reading a paper which refers to a maximally skewed stable distribution $F(x;1,-1,\pi/2,0)$ . Is there an efficient way to sample from this distribution?
If $X$ has distribution $F(x;\alpha,\...
3
votes
1
answer
283
views
Generalization of notion of convexity
I am searching for the correct term for the following, if it exists.
A set $X\subset \mathbb{R}^2$ is called $r$-convex if for any two points $x_1, x_2\in X$ such that there exists an arc of radius $...
3
votes
2
answers
317
views
Combinatorial design for minimization problem over binary strings
Suppose the cost of a binary string $B$ of length $k$ is the number of $1$s that occur before the last $0$. For example, $1110$ has cost 3 while $0111$ has cost 0. Now suppose you can choose $k$ ...
3
votes
1
answer
720
views
Random weighted selection without replacement
I am using the following procedure to select $m$ different numbers $\{i_1,\ldots,i_m\}$ from the set $\Omega = \{1,\ldots,N\}$, with $m,N\in\mathbb{N}$ such that $m< N$.
Selection procedure
...
3
votes
1
answer
434
views
Is there an algorithm to compute group presentations of or find generators for the centralizer of a matrix in $GL(n, \mathbb{Z})$?
Let $M \in H \leq GL(n, \mathbb{Z})$. Is there an algorithm that computes either matrix generators or even a group presentation for $C_H(M)$ given generators or a presentation of $H$? Also is $C_H(M)...
3
votes
1
answer
191
views
Separation of Anti-Hole Inequality
Given an undirected graph $G=(V,E)$ with no loops or multiple edges, a stable set is a set of vertices for which no two vertices are adjacent.
An induced subgraph $H$ of $G$ is called an odd-antihole ...
3
votes
1
answer
355
views
Mathematical Programming with other Algebras than Linear
Linear Programming is strongly entwined with linear algebra, as are many of its generalizations under the heading of mathematical programming / convex optimization.
What analogies are there for ...
3
votes
1
answer
252
views
Breaking frustrated loops in list coloring problem
Suppose we have a graph with $n$ vertices and $n$ lists of colors such that no vertex coloring of the graph using colors from given lists is a proper list coloring. We can characterize the obstacle to ...
3
votes
1
answer
179
views
Algorithm to find a minimal normal subgroup of given group $G$ by matrix group representation
Given a matrix group $G$ by its generators i.e. $G =\langle A_1,A_2,...,A_k \rangle \leq GL_n(q)$, where each $A_i$'s are matrix in $GL_n(q)$
Q. Does there exist a polynomial time (polynomial in ...
3
votes
1
answer
140
views
Maximum weight matching with classes of edges in a multi-edge bipartite graph
Consider a multi-edge bipartite graph $G = (L, R, E)$, with $|L| = |R| = n$, such that any $x \in L, y \in R$ have precisely two edges in $E$, $(x, y)_r, (x,y)_b$. We can imagine that we are assigning ...
3
votes
1
answer
58
views
Wheel-graph with minimal spoke-weight sum centered at a planar-euclidean point
Questions:
Given a set $\mathcal{P}$ of points in the Euclidean plane, what is the complexity of finding for a given point $p_i$ inside the convex hull $\mathrm{CH}\left(\mathcal{P}\right)$ the set $\...
3
votes
2
answers
776
views
Finding a cycle of a specific length in an edge-weighted graph
I'm looking for some suggestions on how we might calculate cycles of a specific length in an edge-weighted graph.
For example, imagine my phone tells me that I need to walk three miles today. It ...
3
votes
1
answer
126
views
Find the smallest circumference of a figure containing n squares [closed]
So there's a figure which contains n squares of 1 x 1, and I have to find the smallest circumference possible. I don't know if there's an algorithm behind this, I've been stuck on this for two hours ...
3
votes
1
answer
133
views
Practical calculation of minimum weight vertex-disjoint cycle covers
How are minimum-weight vertex-disjoint cycle covers of large dense symmetric graphs actually calculated in actual implementations?
I know that the problem can be reduced to general matching by ...
3
votes
1
answer
413
views
What's the runtime of this method and is this method correct?
Let $n=pq$ be the prime decomposition.
I am searching for $l$ such that there exists a $k$ with:
$$n^l = a \cdot 2^k + b$$
and
$$ 1 < \gcd(b,n^l) < n^l$$
Edit by comment of @GerryMyerson:
If $...
3
votes
1
answer
269
views
Partitioning vertex set to maximize weights of inter-class edges?
An interesting problem has come up in my work, and I haven't quite been able to find references to it so I thought I'd ask here.
Suppose we have some complete, weighted graph with vertex set $V$. Is ...
3
votes
1
answer
232
views
computational complexity: do we gain acceleration?
There is a technique we developed for series acceleration using the Wilf-Zeilberger method. Here is a simple Maple code in this regard, you need to download this too.
The idea is you start with a WZ-...
3
votes
1
answer
65
views
Efficient evaluation of this correlation measure
What do you think would be the most efficient way of evaluating the following expression?
Given a binary sequence $ E_N = (e_1,...,e_N) \in \{ -1,+1 \}^N $, and for $D = (d_1,d_2)$ with non-...
3
votes
2
answers
657
views
Algorithms for Sorting Subset Sums
In this question the number of unique sortings has been discussed.
As a follow-up, I would like to know, whether the problem of sorting the sequence of subset sums has ever been studied.
There ...
3
votes
1
answer
159
views
Mestre-type algorithm for higher-genus curves?
Is there an analogous algorithm for genus $g>2$ curves that, given a complete set of invariants, outputs a curve with those invariants?
(I'm interested in particular in $g=3$.)
Any references ...
3
votes
1
answer
336
views
Coloring algorithm maximising color difference between neighbors
Consider a graph and a set of ordered colors ${\cal C} = \{1,2,\cdots,C\}$. I want to color each node $i$ with a color $c_i\in{\cal C}$ so as to maximize the minimum color difference between two ...
3
votes
2
answers
167
views
All Integers from the Smallest Digit Stream with a Window Filter
Let's represent integers with D digits where each digit has B values
(i.e., the base is B and we effectively work only with integers between
1 and B^D). Is it possible to choose a single cyclic/...
3
votes
1
answer
443
views
How to perform Importance Sampling with Prior Information
Let us define a random variable $X$ with density function $p(x)$. We wish to calculate $\mathbb{E}[f(X)] = \int f(x)p(x)dx$. We can compute the expectation by Monte Carlo simulations as
$$\mathbb{E}[...
3
votes
1
answer
494
views
Fastest Digit Extraction for Any Irrational Number
I believe the current lowest-memory algorithm for computing the $n^{th}$ binary digit of $\pi$ requires $O(log(n))$ bytes and $O(n^2 log(n))$ days (I pick Bellard over Bailey–Borwein–Plouffe for speed)...
3
votes
1
answer
142
views
Median-of-k elements
Hello,
Assume I am given a sequence of $n$ elements (by sequence I mean an ordered set). I want to randomly pick $k$ elements out of these $n$ elements, where $k$ is an odd number $\leq n$.
Then out ...
3
votes
2
answers
398
views
A natural problem on "cartesian union" of set families (hypergraphs). Are there NP-complete problems related to the notion of cartesian product?
I'm curious whether the problem below is NP-complete.
I provide two simple definitions and one example at first.
Definition 1.
Let $\langle \cal S_i\rangle\substack{i\in I}$ and $\langle \cal S_j \...