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.

Filter by
Sorted by
Tagged with
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?
Turbo's user avatar
  • 13.7k
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 ...
ilia's user avatar
  • 153
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 ...
Dudi Frid's user avatar
  • 255
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 ...
Jeremy Martin's user avatar
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 ...
Manfred Weis's user avatar
  • 12.6k
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 ...
Yijun Yuan's user avatar
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 ...
benblumsmith's user avatar
  • 2,831
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,...
Xorwell's user avatar
  • 434
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 $(...
Brendan McKay's user avatar
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 ...
Joce's user avatar
  • 131
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 ...
Manfred Weis's user avatar
  • 12.6k
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 ...
Matthias Goergens's user avatar
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 ...
nvcleemp's user avatar
  • 563
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 ...
antianticamper's user avatar
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"...
Alexander Chervov's user avatar
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 ...
Alan Guo's user avatar
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 ...
Mikola's user avatar
  • 2,342
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 ...
didest's user avatar
  • 1,015
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 ...
Patrik Pavic's user avatar
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 ...
Martin Rubey's user avatar
  • 5,533
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,...
Dmitrij Shahlov's user avatar
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)....
Node.JS's user avatar
  • 133
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 ...
MatrixManAtYrService's user avatar
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, ...
Ahsim's user avatar
  • 31
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,\...
Simd's user avatar
  • 3,195
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 $...
Fedor Nikitin's user avatar
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$ ...
Rodrigo Castro's user avatar
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 ...
Paglia's user avatar
  • 807
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)...
user41149's user avatar
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 ...
Fran's user avatar
  • 41
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 ...
DoubleJay's user avatar
  • 2,353
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 ...
Yaroslav Bulatov's user avatar
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 ...
Jins's user avatar
  • 151
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 ...
arealguru's user avatar
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 $\...
Manfred Weis's user avatar
  • 12.6k
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 ...
Rhyd Lewis's user avatar
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 ...
Jimmy's user avatar
  • 31
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 ...
Manfred Weis's user avatar
  • 12.6k
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 $...
user avatar
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 ...
bumbling-tadpole's user avatar
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-...
T. Amdeberhan's user avatar
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-...
Mango's user avatar
  • 31
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 ...
Manfred Weis's user avatar
  • 12.6k
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 ...
user115957's user avatar
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 ...
lchen's user avatar
  • 459
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/...
bobuhito's user avatar
  • 1,537
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}[...
user123884's user avatar
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)...
bobuhito's user avatar
  • 1,537
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 ...
AntiClimacus's user avatar
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 \...
Martin's user avatar
  • 41

1
13 14
15
16 17
32