# Tagged Questions

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

**9**

votes

**0**answers

81 views

### Factoring polynomials over the abelian closure of the rationals

What algorithms are known to perform the following task?
Input: a univariate polynomial over the rationals $f \in \mathbb{Q}[t]$.
Output: the factorization of $f$ into irreducible factors over the ...

**5**

votes

**0**answers

120 views

+50

### Fast convolution of sparse functions

Let $F:\mathbb{R}\to \mathbb{Z}$ be a step function with at most $k$ discontinuities, at given rationals $a_1<a_2<\dotsc<a_k$. Let $g:\mathbb{R}\to \mathbb{Z}$ be given as a linear ...

**0**

votes

**0**answers

22 views

### Proof of a greedy algorithm concerning “Buy and Resell Problem” [closed]

"Buy and Resell Problem" is a classical optimization problem. It can be described in the following way:
There are $n$ cities. For each city, the price of products in this city is given (a positive ...

**3**

votes

**0**answers

76 views

### Generating a Penrose tessellation around a given tile

Given a starting Penrose tile, I need to build a "spiraling" tessellation around it.
The following picture illustrates the request:
In this example, the starting tile is a "thin rhombus" (the pink ...

**4**

votes

**2**answers

203 views

### Fast projection onto a subspace

Given an $n$-dimensional vector $\mathbf{c}\in [0,1]^n$, let $\Delta_{\mathbf{c}}$ be the set of points $\{\mathbf{x}\in [0,1]^n: \langle \mathbf{c},\mathbf{x} \rangle \le 1\}$, where $\langle \mathbf{...

**2**

votes

**1**answer

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

**1**

vote

**0**answers

47 views

### Computational complexity for spectral radius of symmetric matrix

What is the best known algorithmic complexity for computing the spectral radius (largest eigenvalue in magnitude, possibly with respect to some precision and confidence) of a symmetric matrix of size $...

**2**

votes

**0**answers

82 views

### Algorithm detecting all distinct k-th powers in a string for all k ≥ 3

In string theory, the $k$-th power of a string $w$ is named as $w^k$, where $w^0$ is the empty string $\epsilon$ and $w^n$ is the concatenation of $w$ and $w^{n - 1}$ $(n \in \mathbb{N}^{+})$.
The ...

**0**

votes

**0**answers

36 views

### A name for algorithms that perform well in an asymptotic sense, when inputs are random

Is there a term for an algorithm that performs "well" (say, within a constant factor of optimality) in an asymptotic sense when a large number of random inputs are provided? For example, say I had an ...

**0**

votes

**1**answer

67 views

### Sampling a uniformly distributed point INSIDE a hypersphere?

There is a simple algorithm to pick a random point ON an $n$-dimensional hypersphere.
Is there one to sample a point from inside it? (Sampling points from a hypercube and rejecting them if they are ...

**2**

votes

**0**answers

53 views

### Recovering a rank-one matrix from its eigendecomposition after randomized rounding

Let $A = xy^T$ be a rank-$1$ matrix, and suppose every entry of $A$ is in $[0,1]$. We can create a binary matrix $A_{\rm rounded}$ by setting
$$ [A_{\rm rounded}]_{ij} = \begin{cases} 1 & \mbox{ ...

**38**

votes

**1**answer

650 views

### How to be rigorous about combinatorial algorithms?

1. The question
This may be the worst question I've ever posed on MathOverflow: broad,
open-ended and likely to produce heat. Yet, I think any progress that will be
made here will be extremely useful ...

**0**

votes

**0**answers

49 views

### algorithm for maximum sum from root to leaf in a tree (non-binary)

Given some tree with vertices each that can have some variable number of children, is there some algorithm to find the maximum sum from the top of the tree down to one of the leaves? I can see one way ...

**2**

votes

**0**answers

44 views

### First order methods for a large scale semidefinite program [migrated]

I am interested in solving the following semidefinite optimization problem:
\begin{equation}
\begin{split}
\underset{X,\lambda}{\rm maximize} \;\;\;\;&\lambda^Tc \\
&-\mathbb{I} \le X \le \...

**5**

votes

**3**answers

189 views

### Algorithm to decide if the union of a set system covers the power set

Assume that we have a set system $\mathfrak T = \{\mathcal T_1, \mathcal T_2, \dots, \mathcal T_N \}$ where each $\mathcal T_k$ is a collection of subsets of $[n] := \{1,\dots,n\}$ of the form
$$ \...

**2**

votes

**1**answer

178 views

### Name and Algorithms for a Sparsest Circle Packing

The ordinary circle packing problem in the variant with equal radii asks for the largest radius $r_{max}$ that allows placing $n$ non-overlapping circles with radius $r_{max}$ e.g. in the unit square, ...

**0**

votes

**0**answers

29 views

### Partitioning ordered objects into sets so as to maximize isolated objects

I'll phrase this as how I thought of it:
Henri is a headmaster who is planning a school trip. He has ordered $n$ coaches to take his $m$ students to the trip destination, and the students have ...

**1**

vote

**0**answers

67 views

### Loopless algorithm for generating permutations (Steinhaus-Johnson-Trotter)

The following is a description of the well-known Steinhaus-Johnson-Trotter algorithm to generate all permutations of an $n$-element ground set using adjacent transpositions.
In fact, it is a loopless ...

**1**

vote

**1**answer

84 views

### An variation of an assignment problem in combinatorics: assign items to customers

Suppose we want to assign $n$ items to $m$ customers ($n \geq m$). Each assignment of an item $i$ to a customer $j$ has an associated cost $c(i,j)$. Find an assignment that maximizes the total cost. ...

**0**

votes

**0**answers

30 views

### Edgebreaker algorithm over 2-manifolds

Suppose I triangulate a 2-manifold and make a dual pseudograph over it. If I do the Edgebreaker compression algorithm over this graph to generate a spanning tree, can exist an edge with three or more ...

**6**

votes

**0**answers

55 views

### Deciding positivity of real cyclotomic numbers efficiently

Consider a cyclotomic field $\mathbb{Q}[\zeta_n]$ for fixed $n$ and assume that an embedding $\mathbb{Q}[\zeta_n] \hookrightarrow \mathbb{C}$ has been chosen, say by fixing once and for all $\zeta_n=\...

**1**

vote

**0**answers

19 views

### How to express free Lie algebra elements in terms of the right-normed basis?

Article A right normed basis for free Lie algebras and Lyndon–Shirshov words shows that it is possible to build right-normed (right-nested) basis of a free Lie algebra.
I am looking for references (...

**4**

votes

**2**answers

165 views

### Example of concrete statement which requires probabilistic algorithm

In my paper I would like to include an example of easy concrete finitary statement which can be easily verified by probabilistic algorithm to any reasonable confidence level, but which looks ...

**1**

vote

**0**answers

63 views

### Bipartite clustering is NP-hard?

Let $G = (A\cup B, E)$ be a bipartite graph with edge weights $w: E\to \mathbb{R}$. Find a partition $B_1, B_2$ of $B$ and a nonempty disjoint subsets $A_1, A_2$ of $A$ such that $w(A_1,B_1) + w(A_2, ...

**10**

votes

**0**answers

151 views

### Fast computation of matrix product $AXA^T$ with fixed $A$?

Suppose we have two $n$-by-$n$ matrices $X$ and $A$, where $A$ is known and $X$ may change in different invocations, and we want to compute $AXA^T$. Is there an algorithm that beats the naive one of ...

**3**

votes

**1**answer

100 views

### Strong polynomial algorithm for linear programming

What is the current state of finding a strong polynomial algorithm for linear programming? Is there any reference?

**9**

votes

**1**answer

168 views

### Find closest integers in Euclidean rings

Assume that $K$ is a number field such that $\mathcal{O}_K$ is a norm-Euclidean ring. I am looking for an efficient algorithm that given an element $x\in K$, find an integer $y\in\mathcal{O}_K$ that ...

**2**

votes

**0**answers

122 views

### An algorithm to compute coherent sheaf cohomology in projective space over a ring [closed]

EDIT: As the article was put on hold, because it was unclear what I am asking, here I put again my two questions:
1) Is the argument I used to derive the algorithm valid?
The second question is a ...

**0**

votes

**0**answers

15 views

### Calculation of Vertex Weights for Combinatorial Optimization of Regular Spanners

Vertex Weights are a means to modify the weight of an edge by adding to it the weights of its adjacent vertices. The motivation for adding vertex weights to edge weights is two-fold: the relative ...

**1**

vote

**1**answer

152 views

### How to create a quantum algorithm that produces 2 n-bit sequences with equal number of 1-bits?

I am interested in a quantum algorithm that has the following characteristics:
output = 2n bits OR 2 sets of n bits (e.g. 2 x 3 bits)
the number of 1-bits in the first set of n-bits must be equal ...

**6**

votes

**1**answer

293 views

### De-Nesting Absolute Value Function into Linear Combination of Absolute Value Functions

Context: In formulating problems for secondary school mathematics teachers (and students) about absolute value functions, which we define as functions $\mathbb{R} \rightarrow \mathbb{R}$ that send $x \...

**2**

votes

**0**answers

147 views

### Factoring problem similar to $RSA$ structure that is possibly not $NP$ complete and not $coNP$ also?

Standard factoring problem $\Pi_1$ is 'Given integers $N$ and $M$ is there a factor $d\in[1,M]$ of $N$?'. This is in $NP$ since such a factor is the witness and in $coNP$ since one can check all the ...

**1**

vote

**0**answers

95 views

### Is the partition of bipartite graphs NP-hard?

I wonder if the following problem is NP-hard. Is it?
Given a bipartite graph $G = (U, V, E)$ with weights $w : E \to \mathbb{R}_+$, find a partition of $U$ into $U_1, U_2$ and nonempty disjoint ...

**4**

votes

**1**answer

121 views

### sets of partitions associating any two elements exactly once

There may be a theory that deals with problems like this but I'm not
enough of a mathematician to know what it is. So far I've looked up
braid groups, block design, and the recommended related posts ...

**0**

votes

**0**answers

63 views

### Faster Mixed Integer Linear Programming Searchless Feasibility

We know Lenstra's Mixed Integer LP with Kannan's modificiation solves feasibility Mixed Integer LP in $n$ integer variables, $r$ real variables and $m$ constraints by solving the search version in $n^{...

**0**

votes

**1**answer

74 views

### Description of Linear Time Algorithm for TSP in Halin Graphs

I am looking for a description of the linear time algorithm for the TSP in Halin graphs, that was given in
"G. Cornuejols, D. Naddef, and W.R. Pulleyblank. Halin graphs and the travelling ...

**1**

vote

**1**answer

104 views

### Parametric constrained optimization

I'd like to find a way of determining if the distance from the origin of a parametric parabolic path falls below a certain value within a given range of the parameter. The parabola is expressed as:
$$...

**2**

votes

**1**answer

281 views

### Efficient sum of squares decomposition

Sum of 4 squares decomposition is the well-known result. I'm interested only in negative/non-negative separation with focus on efficiency and large numbers. I'm looking for alternatives or extensions ...

**0**

votes

**0**answers

16 views

### Algorithms for Simple Paths with Minimum Cost-to-Time Ratio

This question is related to Graph-theoretic Algorithm for Path with Minimum Average Edge Length, but in this one is about the LP formulation.
Preconditional "facts":
Linear fractional ...

**2**

votes

**0**answers

24 views

### Known Methods for “Mutexing” Antiparallel Arcs in Graphs

I recently faced the problem of calculating shortest paths in undirected graphs in the presence of negative edge weights; I could not find any applicable algorithms via online search.
Transforming ...

**3**

votes

**0**answers

30 views

### Constructing a graph with a given number of edges and a given triangle distribution

Give a number of edges $|E|$, number of vertices $|V|$ and a $|V|\times 1$ vector of integers $T=[t_1, \cdots, t_{|V|}]$, I wish to construct an undirected graph with $|V|$ vertices, $|E|$ edges such ...

**0**

votes

**0**answers

36 views

### Graph-theoretic Algorithm for Path with Minimum Average Edge Length

I am looking for a graph-theoretic algorithm, that determines among all simple paths $\mathcal{P}_{ab}$ that connect vertex $a$ with vertex $b$ the one, that has minimal average edge-length, i.e. $$\ ...

**5**

votes

**1**answer

82 views

### Looking for a tractable algorithm or formula for the determinant of a tensor

It is possible to define the determinant of a tensor.
We think of a tensor as a collection of numbers but this collection easily extends to a proper multilinear map.
If $T:\{1,....,n\}^m\to \mathbb C$ ...

**0**

votes

**0**answers

20 views

### Can the coordinate system in a three dimensional space be corrected for the maximum function when using the simplex algorithm?

Tldr: Is it possible to somehow correct a coordinate system by the maximization function when using the simplex algorithm so it would be possible to just always follow the steepest slope from point to ...

**1**

vote

**0**answers

16 views

### Weight-optimal Union of Edge-disjoint Spanning Trees

I am looking for information about graphs, that are the union of $k$ edge-disjoint spanning trees "EDSP" of finite symmetric graphs. I am especially interested in theorems and algorithms related to ...

**0**

votes

**0**answers

24 views

### Does Barvinok's algorithm count modulo $q$ in $O(polylog (q))$ word size?

Let $Ax\leq b$ be a polyhedron in $n$-dimensions and $m$ constraints and $q>1$ be an integer. The number of points in the polyhedron could be exponential in $n$ and $m$ while $q\ll nm$ could be ...

**3**

votes

**0**answers

94 views

### Topology Data Analysis - faster algorithm

The Topology Data Analysis uses the Mapper algorithm, but computational complexity is not good. Is there an alternative algorithm for algorithm Mapper? Is there an algorithm that works faster?

**3**

votes

**1**answer

73 views

### A question regarding the all pair shortest paths in weighted planar graphs

What is the time complexity of the fastest known algorithm for the all-pair shortest paths in planar graphs?

**0**

votes

**1**answer

154 views

### How to play the following game?

Let $n,k\in\mathbb N$, $x\in(0,1/2)$.
You start $n$ empty bins; each can accommodate at most $k$ balls.
At each iteration, you choose an $x$ fraction of the non-full bins and add one ball to each. (...

**1**

vote

**0**answers

74 views

### Search strategy for Babson task in chess

I asked this on a computer chess forum (programmers hang out there, etc.) and got no substantive answers, which makes me think it's a research question. Whether it's sufficiently mathematical is ...