The algorithms tag has no wiki summary.

**-6**

votes

**0**answers

33 views

### formula for turning star reviews into upvotes [on hold]

I want to turn reviews of up to 5 stars and the number of reviews into upvotes. Whats a good algorithm for doing this?
A venue with 10 reviews total with a 5 star average rating should obviously get ...

**6**

votes

**4**answers

315 views

### Expected value of a function over random sets

I am doing an analysis on the complexity of some set-related algorithm where the input is a random set. One of my setbacks can be formulated as follows:
Pick $k$ distinct numbers out of numbers ...

**0**

votes

**1**answer

166 views

### Efficient isomorphic subgraph matching with similarity scores

I'm a computer vision PhD student, and I'm looking for an efficient approximation to the following problem, which could end up helping in image to image matching. Failing that, pointers to relevant ...

**2**

votes

**0**answers

144 views

### Are there any interesting open questions having to do with submodularity, specially in the intersection of theoretical machine learning? [closed]

I was interested in knowing about open research topics related with sub modularity, specially within its intersection with theoretical machine learning (and related topics).
It seems to me that much ...

**2**

votes

**1**answer

102 views

### Coloring algorithm maximising color difference between neighbors

Consider a graph and a set of ordered colors ${\cal C} = \{1,2,\cdots,C\}$. I want to color each node $i$ with a color $c_i\in{\cal C}$ so as to maximize the minimum color difference between two ...

**3**

votes

**1**answer

691 views

### Efficient algorithms to determine the roots of: $p(x) = r^x $ in the finite field $GF(q)$, where $r$ a primitive root of the field

I need to make sure that no efficient (i.e., polynomial time) algorithm exists for the following problem:
Exponentiating Polynomial Root Problem (EPRP)
Let $p(x)$ be a polynomial with $\deg(p) \geq ...

**2**

votes

**1**answer

52 views

### Is there any algorithm can find local minima of nonconvex objective function in guaranteed polynomial time?

More precisely, The setting could be formulated as,
$min. F_{\lambda}(p)$ over permutation matrices $P$
Here $F_{\lambda}(p)$=$\lambda *F_{0}(p)+(1-\lambda)F_{1}(p)$
where both $F_{0}(p)$ and ...

**3**

votes

**2**answers

725 views

### algorithm for solving systems of linear Diophantine inequalities

So, I posted on stack overflow looking for a reasonably fast algorithm to solve systems of linear Diophantine inequalities and was pointed to this article by Cheng-Zhi Gao and Yu-Lin Dong. The problem ...

**5**

votes

**0**answers

193 views

### When does a “stable” assignment of buyers into goods exist?

Consider a setting of $n$ buyers and $m$ goods.
We have a value matrix $V\in[0,1]^{n\times m}$ specifying how much each buyer values each good (everything is open information here and there is no ...

**11**

votes

**1**answer

726 views

### A generalization of the triangle counting problem for simple weighted graphs

One nice identity is $$tr(A^3)/6$$ which counts the number of triangles of a graph represented with adjacency matrix $A.$ It also implies that triangle counting can be performed in subcubic time.
...

**-1**

votes

**0**answers

12 views

### Three-Dimensional Sokoban solver [migrated]

I'm developing a Sokoban clone as an interactive 3D computer game using Unity engine and C#. I would like to know if anyone has previously tried to develop it. If yes, what's the best algorithm and ...

**8**

votes

**0**answers

224 views

### Is it decidable whether a finite type scheme is proper?

Let $k$ be a field and let $X$ be a finite type scheme over $k$, explicitly given by finitely many affine patches which are $\mathrm{Spec}$ of finitely generated $k$-algebras, glued along other affine ...

**2**

votes

**1**answer

66 views

### Future-Proof Encrypt for Multiple Independent Parties

I have a secret message which I want to encrypt such that any of several different keys can open it independently. The keys can't know about each other and it has to be able to work completely ...

**3**

votes

**1**answer

213 views

### A natural problem on “cartesian union” of set families (hypergraphs). Does anybody know NP-complete problems related to the notion of cartesian product?

I'm curious whether the problem below is NP-complete.
I provide two simple definitions and one example at first.
Definition 1.
Let $\langle {\cal{S}}_i\rangle\substack{i\in I}$ and $\langle ...

**5**

votes

**1**answer

138 views

### Find subset of collection of sets whose intersection has minimum average value

Let $a_1,\ldots,a_n>0$, and let $S_1,\ldots,S_d\subset\{1,\ldots,n\}$ (all non-empty).
For any $I\subseteq\{1,\ldots,d\}$, define $S(I)=\bigcap_{i\in I} S_i$.
Given some $1\leq s < d$, consider ...

**10**

votes

**4**answers

2k views

### Algorithm to check is representation irreducible ? Algorithm to decompose the reducible one ?

Question 1 Given a representation of a finite group, what algorithm can be used to check is it irreducible or not ?
(Main case - complex numbers, comments on other cases are also welcome. "Given" ...

**3**

votes

**1**answer

95 views

### Directed Hypercube Minimal Cuts

If $[n]:=\{1,2,\ldots, n\}$ for some $n\in\mathbb{N}$, then the hypercube digraph of dimension $n$, denoted $H_n$, is the graph whose set of vertices is the power-set $\wp([n])$ where two vertices ...

**4**

votes

**1**answer

346 views

### How to test if the power of some algebraic number is the rational combination of two specific algebraic numbers?

Suppose we are given three algebraic numbers $\alpha,\beta,\gamma$ by presenting their minimal polynomial (degree less than $m$), the goal is to compute all positive integers $n$ such that $\alpha^n$ ...

**12**

votes

**1**answer

508 views

### Constructive proof of “Projective implies proper”

For every ring $A$, the structural morphism of schemes $\pi_A : {\bf P}^n_{A} \to {\rm Spec}{A}$ is a closed map. The usual proof of this fact is not constructive : given equations of a closed subset ...

**1**

vote

**1**answer

67 views

### Finding Laurent Series of a function [closed]

I've been assigned to write a computer program which then calculates the Laurent series of a function. Of course I'm familiar with the concept, but I've always calculated the Laurent series in an ad ...

**0**

votes

**0**answers

49 views

### Generating alternating cycles on a perfect matching

Given a perfect matching $M$ in a regular bipartite graph $G$, is there an efficient algorithm to randomly generate self-avoiding alternating cycles with uniform distribution? Ideally, such an ...

**4**

votes

**2**answers

202 views

### An algorithm to compare two representations of a simple Lie algebra?

I have two representations of a simple (complex or real) finite-dimensional Lie algebra $S$, both given in terms of their structure constants on a given basis.
the first one is the adjoint ...

**1**

vote

**1**answer

81 views

### Computation Complexity for Golden Section method

I need to provide computational complexity for the algorithms in my work. One of the algorithms I have used is Golden Section method for line search. I took a look at "Nonlinear Programming" book by ...

**22**

votes

**0**answers

628 views

### On certain representations of algebraic numbers in terms of trigonometric functions

Let's say that a real number has a simple trigonometric representation, if it can be represented as a product of zero or more rational powers of positive integers and zero or more (positive or ...

**2**

votes

**0**answers

45 views

### Computing maximal ideals of a Lie algebra

Would you know an algorithm (or an automatic method) that computes all maximal ideals $J$ of a given Lie algebra?
Or an algorithm that computes all maximal ideals $J$ containing a given minimal ideal ...

**4**

votes

**2**answers

306 views

### Finding the set of all $0$-$1$ vectors in an affine subspace

We are given a $0$-$1$ matrix $A$ with constant row and column sum, and we need to find out if there exists a $0$-$1$ vector in the solution space of $Ax = \mathbf{1}$ over $\mathbb{Q}$ (or ...

**2**

votes

**1**answer

191 views

### Minimally intersecting subsets of fixed size

The question I have, is how to generate the following collection of subsets:
Given a set $S$ of size $n$. I want to find a sequence of $k$ subsets of fixed size $m$, $0<m<n$, such that at each ...

**1**

vote

**1**answer

73 views

### QR decomposition of matrix [closed]

I have matrix $M = \begin{pmatrix} A & B \\ B^T & 0\end{pmatrix}$, where $A$ is $N\times N$, $B$ is $N\times 2$ and I have $Q$, $R$ such that $A = QR$. What is the fastest way to find $Q'$ and ...

**5**

votes

**2**answers

190 views

### Compute adjugate matrix over commutative ring

Let $A$ be a $n\times n$ matrix over a commutative ring. I'm looking for a good method to compute its adjugate matrix.
My current approach is to use the Cayley-Hamilton theorem:
$$\text{adj}(A) = ...

**20**

votes

**12**answers

7k views

### What are the Applications of Hypergraphs

Hypergraphs are like simple graphs, except that instead of having edges that only connect 2 vertices, their edges are sets of any number of vertices. This happens to mean that all graphs are just a ...

**16**

votes

**3**answers

1k views

### does the “convolution theorem” apply to weaker algebraic structures?

The Convolution Theorem is often exploited to compute the convolution of two sequences efficiently: take the (discrete) Fourier transform of each sequence, multiply them, and then perform the inverse ...

**7**

votes

**0**answers

135 views

### Is there an infinite increasing sequence of naturals for which Landau's function can be efficiently computed?

Landau's function
$g(n)$ is the largest order of an element of the symmetric group $S_n$.
Equivalently, $g(n)$ is the largest least common multiple (lcm) of any partition of $n$.
In general $g(n)$ is ...

**5**

votes

**2**answers

182 views

### Minimum number of unit fractions to sum up a given positive rational

For any positive $p,q\in\mathbb{N}$ there is a finite subset $S$ of $\{\frac{1}{n}:n\in\mathbb{N}, n\geq 1\}$ such that $\sum_{s\in S} s=\frac{p}{q}$. Let $m(p,q)$ denote the minimal cardinality of ...

**3**

votes

**1**answer

81 views

### Sorting interleaved sorted lists

By interleaving two lists I mean to combine them into a single list in any way that maintains the relative order of the elements coming from each list. For example, interleaving $(x_1,x_2,x_3)$ and ...

**0**

votes

**0**answers

63 views

### Parallelism degree of a DAG

Let me first give a motivation. Suppose a connected DAG G with one source X and one sink Y. The goal is to find some "bottleneck" node between X and Y, i.e. node through which every path from X to Y ...

**23**

votes

**5**answers

1k views

### Securing privacy of “who communicates with whom” under Orwell-like conditions

Assume that there is a big and powerful country with an
information-greedy secret service which has backdoors to all internet nodes
throughout the world which permit him to observe all exchanged data ...

**2**

votes

**1**answer

272 views

### Solving assignment problem using Hungarian method vs min cost max flow problem

The traditional solution for the assignment problem is the Hungarian method - it's complexity is O(V^4) or O(V^3) if using Edmonds method.
However, it can also be reduced to a min cost max flow ...

**0**

votes

**0**answers

118 views

### E- and A-algorithms for finite arithmetic prime progressions and other sets

(EDIT from scratch).
Let $\ \mathbf a := (a_1\ \ldots\ a_n)\ $ be an increasing non-constant arithmetic progression of odd positive numbers. The goal here is to resolve efficiently one of the two ...

**8**

votes

**4**answers

698 views

### What does it mean when we say we have computed a number to a certain accuracy using a probabilistic algorithm?

My intention is to ask a general question about probabilistic (Monte Carlo) algorithms. But to keep things simple, I will focus on a few specific examples.
Let me start the discussion with ...

**1**

vote

**2**answers

194 views

### Regular paths along surface of sphere

I'm trying to create a program where a small ball is supposed to move along the surface of a sphere, which is given by its radius $r$ and the center $c$.
The movement should be repetitive, so that ...

**1**

vote

**0**answers

79 views

### Can we find structure constants of Lie Algebra for Lie Symmetry of ODE without solving determining equations?

Let's consider (for example) one scalar ODE.
We are searching for Lie Symmetries of it.
There is well-known result, that we can find size of Symmetry Group without solving determining equations.
...

**4**

votes

**1**answer

210 views

### convex polyhedron in the unit cube

Let $P$ be a given finite set of points within the $n$-dimensional unit cube. A finite set $Q$ of points within the $n$-dimensional unit cube covers $P$ if $\operatorname{conv}(Q) \supseteq P$ where ...

**15**

votes

**1**answer

3k views

### Conceptual explanation of Strassen's trick for matrix multiplication

Algorithms for fast multiplication of polynomials and integers have well-known conceptual explanations. A good survey paper is Daniel J. Bernstein's Fast Multidigit Multiplication for Mathematicians.
...

**0**

votes

**0**answers

25 views

### how to efficiently compute the mean function for non-homogeneous poisson process?

Suppose that I know all intensity functions lambda(t) during given period [0,t], how can I compute the mean function m(t) for non-homogeneous Poisson process?
Basically, m(t) in the integral of ...

**2**

votes

**0**answers

46 views

### finding dominating cycles in $2K_2$-free graphs

A cycle $C$ in a connected graph $G$ is called dominating if its complement $V(G)-V(C)$ is an independent set. H.J. Veldman proved in 1983 (Disc. Math. v.43, 281-96) a general result that in ...

**7**

votes

**2**answers

4k views

### Partitioning a polygon into convex parts

I'm looking for an algorithm to partition any simple closed polygon into convex sub-polygons--preferably as few as possible.
I know almost nothing about this subject, so I've been searching on Google ...

**1**

vote

**0**answers

60 views

### Max flow with minimal requirements algo problem

While applying the algorithm to solve the max flow of the network with minimal requirements on edges, I have encountered a problem.
The algorithm states:
For graph G
create an edge from target to ...

**3**

votes

**1**answer

129 views

### How to generate $n$ FP32 rationals s.t. no two distinct k-el. subsets have same sum?

First some
Background: I have lots and lots of integer matrices, whose rows are $k$-combinations (without repetitions and sorted) of numbers from the set $S:=\{1,...,n\}$ and needed to be compared ...

**14**

votes

**5**answers

569 views

### Mathematics of privacy?

I wonder to which extent the current public debate on privacy issues (not only by state sniffing, but e.g. by microtargetting ads too an issue) offers interesting questions in mathematics?
Can we ...

**11**

votes

**1**answer

168 views

### Fastest algorithm to compute the width of a poset

An colleague recently came to me with a problem concerning the scheduling of tasks in the presence of constraints (of the kind: task $x$ can't begin until task $y$ has been completed). It turned out ...