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, ...

learn more… | top users | synonyms

3
votes
0answers
22 views

Complexity of OBDD isomorphism (representing same function after permutation of variables)?

According to wikipedia Ordered Binary Decision Diagarams (OBDD) are a data structure that is used to represent a Boolean function. OBDD is a DAG with two sinks $0,1$. The size of the BDD is number ...
11
votes
1answer
686 views

Reasons for difficulty of Graph Isomorphism and why Johnson graphs are important?

In http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/ it is mentioned: 'In discussing Johnson graphs, Babai said they were a source of “unspeakable ...
2
votes
0answers
60 views

Blossoms and Colorings

There is a striking analogy between finding maximum matchings in graphs and determining the chromatic number of graphs: both problems are fairly easy for bipartite graphs, but harder, resp. too hard ...
3
votes
0answers
83 views

Algorithm for finding the fewest cartesian products to partition a set of points

The question Algorithm for finding the fewest rectangles to cover a set of rectangles was already answered here and a similar question was answered here. Those questions were about regular geometric ...
1
vote
1answer
42 views

Test Instances for Perfect Matchings in Graphs

Are there any graphs with a known set of perfect matchings and other predefined properties, such as vertex connectivity, which can be used for testing the implementation of matching algorithms? ...
3
votes
0answers
69 views

What is the influence of unreliable comparisons on the results of sorting

Considering sorting algorithms based solely on binary comparisons of the elements to be sorted(algorithms such as insertion sort, selection sort, quicksort, and so on), what problems do we face when ...
3
votes
2answers
192 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 ...
1
vote
1answer
73 views

What is the relation between size of maximum clique and branchwidth?

Let $bw(G)$ be the branchwidth of graph $G$ and $\omega(G)$ be the size of maximum clique in $G$. I think the following inequality holds: $$ \omega(G)\leq bw(G) $$ Intuition: Assume (in reverse of ...
9
votes
1answer
669 views

Some Questions on the Collatz conjecture

The set of all positive whole numbers is denoted by $\mathbb{N}_+$. Let $f\colon\ \mathbb{N}_+\to\mathbb{N}_+:n\mapsto \begin{cases}\frac{n}{2}&\text{$n$ even}\\3n+1&\text{$n$ ...
1
vote
0answers
63 views

Does Coppersmith's method always finds non-trivial factor of integers of the form $n=a(2^k b+1)$ assuming $1 < a<2^k b +1$ and $b < n^{1/4-0.05}$?

Got an argument and numeric evidence that pari's implementation of Coppersmith's method finds non trivial factor of integers of certain form under some assumptions very efficiently. Three $5000$ bit ...
1
vote
0answers
73 views

Grobner basis for a general algebra

Let $R$ be a quotient of the polynomial ring $\mathbb{C}[x_1,\dots , x_n]$. We fix a $\mathbb{C}^*$ action on $R$ which preserve homogenous components and the multiplication. (The geometric analogue ...
6
votes
1answer
117 views

Algorithm that solves every Mixed Integer Linear Program (to optimality)?

Given a Mixed Integer Linear Program with rational coefficients (both for the objective functions and all constraints), is it always possible to solve it algorithmically? I know that you usually ...
6
votes
0answers
73 views

Correlation of Class Functions

Let $G$ be a finite group, and let $f_1,f_2$ be two real-valued class functions of $G$. Assume that multiplying elements of $G$ takes $O(1)$-time. Let $s:G\to \mathbb{R}$ be defined by ...
0
votes
0answers
25 views

Monotonicity per dimension of multivariate scattered data

For my thesis, I am working on interpolation using the RBF method (Radial Basis Functions). Before interpolating, I want some a priori insight into the data, for example check in which dimensions it ...
4
votes
2answers
161 views

Extraction of Coefficients in the Exponential Function of a Series

Question: Let $f(x) \in x\mathbb{C}[[x]]$. What is the (asymptotically) fastest algorithm for calculating the coefficient of $x^n$ in $e^{f(x)}$? Naive Solution 1: Using fast polynomial ...
6
votes
1answer
267 views

G-Correlation of Vectors

Let $\vec{a},\vec{b} \in \mathbb{R}^{n}$. Consider the function $f: S_n \to \mathbb{R}$ given by $f(\sigma):= \sum_{i=1}^{n} a_i b_{\sigma(i)}$. Let $G$ be a subgroup of $S_n$, given by $O(\log n)$ ...
3
votes
1answer
212 views

Algorithm to count the number of perfect matchings in non planar graph

I need to count the number of perfect matchings of a certain family of graphs. This family of graph is non planar and a type of snark. For the initial cases, it seems that this number is growing ...
4
votes
0answers
177 views

Comparison of Constrained Optimization Methods

I am trying to solve a constrained optimization problem using filter methods and came across two papers on the topic that I am having some problems with. The original filter method paper is the ...
-1
votes
1answer
86 views

Is there an algorithm to find a linear dependence between points on elliptic curves?

Let $E$ be an elliptic curve over a finite field $\mathbb{F}_p$ of characteristic $p$. Let $P,Q\in E(\mathbb{F}_q)$, such that $Q=mP+n\tau(P)$, where $\tau$ is the p-th power of frobenious map and $m$ ...
2
votes
1answer
78 views

Seeking for abelian subalgebra of fixed dimension in finite Lie algebra

The problem is: I want to know if there is abelian subalgebra of dimension $k$ in Lie algebra of dimension $n$. My Lie algebra is given by its structure constant table. There are some algorithms ...
1
vote
2answers
107 views

The cost function in the Weighted Bipartite Matching Problem (a.k.a the Assignment Problem)

In the definition of this problem, the weight/cost function generally takes value in $\mathbb{Z}$ (or sometimes $\mathbb{Q}$). This is what I observed from some books (e.g. "Combinatorial ...
11
votes
1answer
305 views

Travelling salesman: can the furthest-neighbour algorithm beat the nearest-neighbour?

This is a problem that has bugged me for quite some time, and I have not been able to find any documentation about it online. It is well known that the NN algorithm can yield the worst possible route ...
1
vote
0answers
23 views

Performance guarantee of RLF [closed]

I cannot manage to find the performance guarantee of the Recursive Largest First (RLF) algorithm for approximating the chromatic number of a graph. I know DSATUR has a $\mathcal{O}(n)$ guarantee, ...
2
votes
2answers
208 views

$k$-th subset in order of increasing sum

I have an array of integers T[N] indexed from 1. For example T[1] = 1, T[2] = 4, T[3] = 5, T[4] = 9. Let's enumerate all subsets of this set in a certain order: increasing sum of the elements. In case ...
3
votes
2answers
114 views

Computing digits of irrational exponentiation

Let us have positive irrational numbers $a$ and $b$ represented by functions $f_a,f_b\colon\mathbb{N}\to\mathbb{N}$ respectively such that $f_a(0)=\left \lfloor{a}\right \rfloor$ and $f_a(i)$, ...
1
vote
0answers
72 views

Algorithm to generate hyperbolic metric on a compact surface

Let $F$ be a compact surface of genus $g$ with generators $a_1,b_1,\ldots ,a_g,b_g$ with relation $[a_1,b_1]\cdots [a_g,b_g]=1$. We can also consider surfaces with boundary in which case the ...
1
vote
3answers
265 views

Finding integer representation as difference of two triangular numbers

Since $n = \frac{n(n+1)}{2}-\frac{n(n-1)}{2}$, every natural number can be represented as the difference of two triangular numbers: $ n = \frac{a(a+1)}{2}-\frac{b(b-1)}{2}$. Finding such a ...
4
votes
0answers
370 views

Weighted Median Filtering

Let's begin with a little review of unweighted median filtering. Suppose I have a list of $N$ real-valued numbers, $x=x_1,...,x_N$. Let $m_i$ be the median of $K$ consecutive values: $m_i=$ ...
5
votes
1answer
56 views

Two fold optimization: is there an established approach for this kind of problem?

I have a list of thousands of linear expressions, with less than 100 total variables. Each expression is associated with a positive point value. I want to make as many of the expressions greater than ...
5
votes
1answer
172 views

Is this subset-sum-type problem discussed in the literature?

Let $y \in \mathbb{Z}_+^n$, with $y_1 < \dots < y_n$. I am interested in finding a 0-1 matrix $A$ and $x \in \mathbb{Z}_+^m$ s.t. $m$ is minimal and $Ax = y$, where I am guaranteed that at least ...
3
votes
2answers
73 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 ...
2
votes
0answers
203 views

Avoiding Chinese Remainder Theorem

Given $k\in\Bbb N$ with $k<(\log_2N)^{\frac1\alpha}$ where $\alpha>2$ is fixed and $N$ being some integer such that $$N<\prod_{i=1}^k\pi_i^{a_i}$$ where $\pi_1,\pi_2,\dots,\pi_{k-1},\pi_k$ ...
7
votes
1answer
264 views

State of the art in the expected length of the Longest Increasing Subsequence of a random permutation

I have been reading about the topic motivated by a problem I read that asked for the first three digits of the sum of the LIS lengths in all permutations of length $n$. It is easy to see that we are ...
1
vote
2answers
65 views

Maximum subgraph edge distance greater than given number

I have a weighted graph G with approximately 75000 nodes. I would like to find subgraph G' induced on a subset of nodes, such that all edge weights in G' are greater than a given constant C and the ...
8
votes
1answer
694 views

Doob Martingale: Where is the catch?

I am working on a research problem in uncertainty propagation that involves sums of possibly dependent random variables with bounded sets of support. I am attempting to use the method of bounded ...
2
votes
1answer
100 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 ...
0
votes
0answers
107 views

Systems of linear modular equations with unknowns in the moduli

I am interested in systems of linear modular equations, where the unknowns also appear in the moduli. The general form would be: $A \vec{x}= \vec{b} \;\textrm{mod} \; (C \vec{x}+\vec{d})$ where A ...
4
votes
1answer
266 views

Listing all solutions to $n = x^2 + y^2 + z^2 $ with integers

I would like to list all ways of writing $n$ as the sum of 3 squares. This is slightly different from finding just one: Is there an algorithm for writing a number as a sum of three squares? ...
2
votes
1answer
97 views

Asymptotic upper bound for recursive function $f(x) = f(x-1) + 2f\left(\lceil\frac{x}{2}\rceil \right)+2$

I'm looking for an asymptotic upper bound for the function f(x), which is recursively defined as follows: $$f(x) = f(x-1) + 2f\left(\lceil\frac{x}{2}\rceil \right)+2$$ with $f(1)=1$. I am pretty ...
3
votes
1answer
115 views

Construction of planar embedding

I'm reading the following paper on universality considerations in VLSI circuits http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf In Theorem 2 On the second page it states there exists ...
7
votes
3answers
242 views

Embedding planar graphs into the grid

I've seen the following lemma in a paper. The result is by Valiant. A planar graph $G$ with maximum degree $4$ can be embedded in the plane using $O(|V|)$ area in such a way that its vertices are at ...
2
votes
0answers
81 views

Computing the density of a set of multiples

Erdős and his coauthors often wrote about problems relating to the densities of sets of multiples. I have a computational question about the same topic. I have a finite* set $A=a_1<\cdots<a_r$ ...
9
votes
3answers
500 views

Is the Number of Carries in Integer-Addition Associative?

Is it true that the number of carries, when calculating the sum of a finite set of finite positive integers, is constant (i.e. independent of their permutation and the order in which the additions ...
2
votes
0answers
92 views

Worst case performance of a simple averaging algorithm

Let $u_1,\ldots,u_n$ be a sequence of rationals with finite binary expansion. Consider the following simple averaging algorithm: while the sequence is not monotone increasing, pick $i$ with ...
0
votes
0answers
48 views

Finding spanning vector sets

Let $V$ be the set of all vectors over the non-negative integers. For any two subsets $S$ and $T$ of $V$, define $S + T$ to include: All vectors in $S$ All vectors in $T$ All vectors that can be ...
7
votes
2answers
454 views

What is wrong with this deterministic algorithm efficiently generating large primes?

According to PolyMath (Strong) conjecture. There exists deterministic algorithm which, when given an integer k, is guaranteed to find a prime of at least k digits in length of time polynomial in ...
1
vote
0answers
235 views

Reduction to some physical interpretation of this formula

Problem Given N 3-dimensional points which are {$p_1,p_2,..,p_n$} where $p_i = (x_i,y_i,z_i) $ . I have to find the value of the formula $$ \sum \limits_{i=0}^n \sum \limits_{j=i+1}^n \frac{ \mid ...
2
votes
0answers
38 views

Algorithm to get lower peak of bimodal histogram [closed]

I have a set of data, when tabulated in histogram, it looks like bimodal histogram. With naked eyes, we can see the value for lower peak is about -1.35, however, what algorithm I can use to ...
3
votes
3answers
136 views

Algorithm to determine isomorphism of 2 maximal planar graphs

I read on wikipedia that there are efficient algorithms to answer the question whether 2 (maximal) planar graphs F and G are isomorphic. However, after some (IMHO) substantial searching I don't seem ...
2
votes
1answer
109 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 ...