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

2
votes
1answer
69 views

Minimal Support Solutions of a Linear System (Dissertation)

For a given $n \times m$ matrix A with $m>>n$ and a given vector $\vec b \in \mathbb{F}^{n \times 1}$, and given that $A\vec{x}=\vec{b}$ for at least one $\vec{x} \in \mathbb{F}^{m \times ...
1
vote
2answers
51 views

Maximal Minimum Weight DAGs

In the case of undirected, connected graphs the name for the maximal cycle-free subgraph of minimal weight is called Minimum Spanning Tree, and the efficient algorithms for their calculation are well ...
4
votes
0answers
126 views
+50

Complexity of approximating the size of the range of a matrix

Given an $m$ by $n$ matrix $M$ with $m \leq n$ and elements from $\{-1,1\}$, let us define: $$S_M = |\{Mx : x \in \{-1,1\}^n\}.$$ It is NP-hard to compute $S_M$ exactly I believe by applying the ...
-1
votes
0answers
30 views

algorithm to split one real number to 3 variables [closed]

I asked this question on stackoverflow already but maybe it is more math related. I try to store integer (real numbers) values into pixel data. The only way my api can store pixel data are RGB ...
4
votes
1answer
170 views

Polynomial factoring over finite fields

What is known in general about the complexity of factoring polynomials over finite fields? For instance given $\Bbb F_q$ where $q=p^n$ and total degree $d$ polynomial in $m$ variables what can we say ...
2
votes
0answers
58 views

Detecting Negative Cycles in Undirected Graphs

I recently faced the problem of quickly detecting negative cycles in undirected, weighted graphs. Resorting to the Bellman-Ford Algorithm, as commonly suggested, turned out to be very inefficient and ...
2
votes
0answers
45 views

Is there a name for this variant of the MST and the TSP?

Suppose I am given a weighted graph $G$ that contains a "start vertex" $v_0$, and my goal is to construct a set of paths that all originate at $v_0$ and touch all of the vertices of $G$, with as ...
9
votes
1answer
174 views

Exact determinant of a circulant matrix

The wikipedia gives us a formula for the determinant of a circulant matrix. That is: $$\mathrm{det}(C) = \prod_{j=0}^{n-1} (c_0 + c_{n-1} \omega_j + c_{n-2} \omega_j^2 + \dots + c_1\omega_j^{n-1})= ...
3
votes
0answers
71 views

Is there a Havel-Hakimi for geometric graphs?

Suppose that we are given $n$ points in the plane, with a degree prescribed for each, and the question is whether we can place a geometric graph on them. Is there an efficient algorithm for this? ...
2
votes
1answer
100 views

Does anyone have the correct link to treewidth.com?

Several posts (and this) on StackExchange sites like MO have some link-rot. For example, I've been looking into tree decomposition and keep coming across references to treewidth.com, but the link ...
3
votes
0answers
12 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
631 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
49 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
72 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
35 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
58 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
149 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 ...
8
votes
1answer
455 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
55 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 ...
0
votes
0answers
65 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
91 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
71 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
23 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
141 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
266 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
154 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
169 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
82 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 ...
0
votes
1answer
77 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
285 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
22 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
171 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
107 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
258 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
199 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
52 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
168 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
63 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
197 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
231 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
56 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 ...
7
votes
1answer
473 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
99 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
75 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
256 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
90 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
110 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 ...