# Tagged Questions

**2**

votes

**1**answer

43 views

### Area of an irregular, n-sided, non-intersecting (edges) polygon algorithm

I need to generate an irregular, n-sided polygon of non-intersecting edges (n= 200, for example) with the smallest area possible. The position of the vertex is random and I've tried designing a couple ...

**-1**

votes

**1**answer

36 views

### Computing the inverse of a Cholesky decomposition [on hold]

I have chol(A) and I would like chol(A^-1). One way to do this is to construct the inverse positive definite symmetric matrix and then take its Cholesky decomposition (with Dpotri and Dpotrf for ...

**2**

votes

**1**answer

70 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

**2**answers

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

**6**

votes

**0**answers

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

**4**

votes

**1**answer

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

**0**answers

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

**0**answers

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

**1**answer

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

**0**answers

72 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

**1**answer

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

**0**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**2**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**2**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**2**answers

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

**2**answers

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

**0**answers

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

**3**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**2**answers

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

**0**answers

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

**1**answer

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

**2**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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