Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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
0answers
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
0answers
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
0answers
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
0answers
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
2answers
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
3answers
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
2answers
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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 ...