Questions tagged [algorithms]

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-randomness and algorithmic-topology tags.

Filter by
Sorted by
Tagged with
3
votes
1answer
111 views

Finding a binary variable assignment to make a matrix with variables singular (over F_p)

Consider a square matrix defined over a finite field $M\in\mathbb{F}_p^{n\times n}$ having the following form $$M=\begin{bmatrix}a_{11}+b_{11}x_1&a_{12}+b_{12}x_1&\dots&a_{1n}+b_{1n}x_1\\...
2
votes
0answers
75 views

How hard is this combinatorial optimisation problem?

Suppose we have multiple ranges $R_1,R_2,...,R_i$ of non-negative integers. These ranges may overlap and we use $R_h(\mathrm{median})$ to denote the median integer in the $h$-th range $R_h$, and $x_R$ ...
0
votes
2answers
352 views

mathematics around ranking [closed]

Is there interesting mathematics around ranking? (I mean ranking as reputation points here at mathoverflow.) It looks obvious that there is no way to make adequate ranking --- is it a theorem, at ...
3
votes
1answer
167 views

Difference set of difference set

I am a hobby computer scientist and searching for an algorithm to construct a set of n numbers (integers) with certain properties. Property 1 / Step 1 All pairwise differences of the elements should ...
1
vote
1answer
66 views

Knapsack problem with capacity constraint

The traditional knapsack problem is that: given a sequence of $i$ items with positive weights $w_1,w_2,...,w_i$, positive values $v_1,v_2,...,v_i$, and a bag with capacity $B$, we want to insert items ...
1
vote
1answer
136 views

Complexity of a Diophantine equation having $\leq1$ solutions

We are provided a single Diophantine equation $$f(x_1,\dots,x_n)=0$$ having degree $\geq2$ and having the promise it has $\leq1$ solutions in the set $\{0,\dots,m-1\}^n$ and $t$ is the number of terms ...
2
votes
1answer
123 views

A fast algorithm for a probabilistic counting problem without replacement?

Consider the integers $\{1,\dots, N\}$ for some positive integer $N$. Let us suppose that for each $\{1, \dots, N\}$ there is an associated probability $p_1, \dots, p_N$. We also define an integer ...
2
votes
1answer
141 views

The “best way” to order unknowns in linear systems

Start with a linear system of the form \begin{equation*} Ax + Bt + C = 0, \end{equation*} where $x = (x_1, \dots, x_n) \in \mathbb R^n$ is the vector of unknowns, $t \in \mathbb R^m$ is a vector of ...
0
votes
0answers
121 views

Algorithm to compute automorphism group of a finite group

Is there an algorithm to compute automorphism group of a finite group? GAP has a function to do this, but while perusing their GitHub repo, I could not find an implementation. I'm struggling to find ...
1
vote
0answers
63 views

Fastest algorithm to construct a proper edge $(\Delta(G)+1)$-coloring of a simple graph

A proper edge coloring is a coloring of the edges of a graph so that adjacent edges receive distinct colors. Vizing's theorem states that every simple graph $G$ has a proper edge coloring using at ...
1
vote
0answers
90 views

Integrality of polyhedra

Given two polyhedra in $H$ representation $P_1:Ax\leq b$ and $P_2:Bx\leq c$ which are integral are bounded when is their intersection also integral? Given two polyhedra in $H$ representation $P_1:Ax\...
1
vote
1answer
35 views

$\mathrm{LP}$ formulation for $\mathrm{k}$-$\operatorname{opt}$ moves

$\mathrm{k}$-$\operatorname{opt}$ moves are an idea to improve non-optimal Hamilton cycles in weighted symmetric graphs by exchanging $\mathrm{k}$ tour-edges with $\mathrm{k}$ edges that do not belong ...
2
votes
1answer
177 views

Find a collection of values of polynomial

Given a polynomial $f(x)\in \mathbb C[x]$ where $\deg f(x)=n-1.$ Assume that we need to find a collection of values of this polynomial corresponding to the following set of $x$-values: $\{ e^{ik} \}$ ...
2
votes
1answer
111 views

Directed version of this lemma

On a paper by Shoham Letzter, available Here, there's a lemma that says as follows: Lemma 0: For every graph $G$, there exist two disjoint sets $U,W\subseteq V(G)$ of equal size, such that there are ...
2
votes
1answer
65 views

Min-sum and min-max node-disjoint path problems

Given an undirected weighted graph, we seek a pair of node-disjoint path between $2$ nodes $s$ and $t$: if the objective is to minimize the total path cost, the Suurballe algorithm can be applied; now ...
1
vote
0answers
20 views

Given a unit vector $x\in\mathbb R^d$, what is the worst possible within-cluster sum of squares for 2-means clustering?

This is a question I originally posted to math.stackexchange.com but it didn't attract any answers, and I was wondering if someone here can help. Consider a unit vector $x\in\mathbb R^d$ ($\|x\|_2=1$)...
4
votes
0answers
110 views

Buchberger's criterion for Gröbner bases in $k$-algebras with multiplicative basis and admissible order

Let $R$ be an associative $k$-algebra with multiplicative basis $\mathcal B$ with an admissible order on $\mathcal B$. Let $G \subseteq R$ be a subset. A multiplicative basis $\mathcal B$ means that $...
14
votes
3answers
271 views

Exact coverability of $\mathbb{Z}_n$ by cyclic shifts of a given set — easy? NP-complete?

Recently Ernest Davis asked me about the following computational problem: we're given as input a composite integer $n$, a divisor $k$ of $n$, and a subset $S \subset \mathbb{Z}_n$ of size k. The ...
0
votes
0answers
52 views

Bijectively parametrize non-negative integers by binary sequences

Given $n\in \mathbb{Z}_{\geq 0}$ denote by $B_n$ the set of binary sequences of length $n$. Denote $B=\bigcup_{n\geq 0} B_n$. Let $P, Q:\mathbb{Z}_{\geq 0}\to\mathbb{Z}_{\geq 0}$ be two computable ...
5
votes
3answers
201 views

Order from Coxeter-Dynkin diagram

How is the order of a Coxeter group determined from its Coxeter-Dynkin diagram?
5
votes
0answers
75 views

Computing the zeta transform of a Boolean function: Space-time tradeoff

Let $f : \mathbb{F}_2^n \to \mathbb{F}_2$ be a Boolean function in $n$ variables. The zeta transform of $f$ is the Boolean function $\zeta_f : \mathbb{F}_2^n \to \mathbb{F}_2$ defined by $$\zeta_f(y) :...
0
votes
0answers
53 views

Primality of $n$ bit integers in depth $n^\alpha$ under standard conjectures?

Denote $\mathsf{NC}(\mathsf{SUBLINDEPTH}(n),f(n))$ to be set of boolean circuits of fan-in $2$ which can be represented by depth $\cap_{\alpha>0}\mathsf{}n^\alpha$ and $f(n)$ sized Boolean circuits....
0
votes
0answers
58 views

Algorithm for computing group inverse of some matrices

I am interested in algorithms (and implementations) for computing the group inverse of $\rho(A)I - A$ of a non-negative irreducible matrix $A$. In the well-cited reference [1], the author describes in ...
4
votes
1answer
85 views

String compression algorithms for simplifying an expression by introducing variables

I have a very long algebraic expression computed with Maple, and when I inspect it visually, it is clear that it consists of a set of terms that appear over and over again. For purposes of human ...
1
vote
1answer
34 views

Relation of 1-trees to optimal tours

Question: given a complete symmetric graph $G(V,E)$ with $n$ vertices and edges $e_{ij}$ having weight $\omega_{ij}$, does there always exists a vector of vertex potentials $(\pi_1,\,\dots,\,\pi_n)$ ...
3
votes
1answer
56 views

Maximum weight matching with classes of edges in a multi-edge bipartite graph

Consider a multi-edge bipartite graph $G = (L, R, E)$, with $|L| = |R| = n$, such that any $x \in L, y \in R$ have precisely two edges in $E$, $(x, y)_r, (x,y)_b$. We can imagine that we are assigning ...
1
vote
1answer
53 views

Proving that a preorder traversal of a rooted tree $T(V, E)$ is $O(\lvert V \rvert)$ [closed]

Definition: Let $T(V, E)$ be a rooted tree with root $r$. If $T$ has no other vertices, then the root by itself constitutes the preorder traversal of $T$. If $\lvert V \rvert > 1$, let $T_1, T_2, \...
0
votes
0answers
42 views

A minimum string contain all the “n-combination”of n different elements(like the Haruhi Problem)

This string is not like the De Brujin sequence,010is equal to 100. and there is a example. Just like the Haruhi Problem. As a DoTa2 player, I like Carl very much. He is a great magician.Carl has three ...
0
votes
0answers
17 views

Deciding unimodular versus a singular matrix

$L$ and $R$ are matrices in $\{0,1\}^{n\times n}$ given to you and one of $L$ and $R$ is singular and the other is unimodular on the identification as a biadjacency of a bipartite graph it has one ...
0
votes
0answers
28 views

Spanning subgraphs defined via $K_4$ matchings

I have by accident found an interesting kind of spanner of complete symmetric graphs $G(V,E)$ with weighted edges. What I actually had planned was to implement an algorithm for calculating certain non-...
2
votes
1answer
139 views

Given an input point in $\mathbb{R}^n$, select (one of) the closest point(s) from a fixed large set of points given in advance

We are given a set $S$ of $m\gg 1$ points in $\mathbb{R}^n$. In the problem I am trying to solve, in a sequential fashion, we obtain a new point $p_r\not\in S$ at each round $r\ge 1$ and the goal is ...
6
votes
4answers
574 views

Computational cost of extracting a proof

Suppose we are studying the Zermelo–Fraenkel set theory as a first-order logic and our metatheory is also the Zermelo–Fraenkel set theory. Is there a statement $P$ such that no direct proof of $P$ ...
3
votes
0answers
56 views

Random graphs with prescibed degrees and triangles

In short: a random graph model generates (multi-)graphs with prescribed number of edges and minimal number of triangles for each vertex. Questions arise about the actual number of triangles and the ...
0
votes
1answer
69 views

Find cycles with specific weights in complete graph

Assume I have an undirected edge-weighted complete graph $G$ of $N$ nodes (every node is connected to every other node, and each edge has an associated weight). Assume that each node has a unique ...
0
votes
0answers
89 views

Writing integers as sequences of products by 2 and integer divisions by 3

For any integer, we consider its decompositions into sequences of products by $2$ and integer division by $3$. For instance: $$ 100 = 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \...
1
vote
0answers
40 views

Algorithm for minimum weight matching with “tree topology”

Given a finite graph $G(V,E)$ with undirected and weighted edges, whose set of vertices $V$ is partitioned into a collection $\mathfrak{P}=\lbrace V_1,\,\dots,\,V_k\rbrace$ of non-empty and pairwise ...
1
vote
1answer
75 views

Geometric sampling problem in the Euclidean space in high dimensions

Let $T$ be the triangle whose vertices are three given points $\mathbf{x}, \mathbf{y}, \mathbf{z}\in\mathbb{R}^d$. Question: What computationally efficient strategy can we use to sample a point $\...
1
vote
0answers
57 views

Generating triangulations with given topology

I am looking for information about the problem of identifying the heaviest minimal subset $F\subset E$ of the edgeset $E$ of a complete symmetric graph $G(V,E)$ with randomly weighted edges such that ...
1
vote
0answers
52 views

Why does Y. Moshe Vardi use this specific matrix when estimating source-destination traffic intensities with EM algorithm?

Sorry for the verbose title, but the question is super specific. If you happen to know a site better suited for these types of question, feel free to direct me. The article to which I am referring to ...
1
vote
2answers
157 views

Sampling method for a specific distribution in high dimensions

We are given a set $X$ of $n$ points $\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n\in\mathbb{R}^d$, where $d\ll n$. Given any point $\mathbf{p}$ on the unit $(d-1)$-sphere $\mathcal{S}$, we define ...
2
votes
0answers
47 views

Are two degree sequences compatible, for random simple graph generation?

Consider a set $V$ of $n$ vertices, and three degree sequences $a_i$, $b_i$ and $c_i$ such that $c_i = a_i+b_i$, $i=1..n$. Assume these degree sequences are graphical: there exist simple graphs (no ...
8
votes
1answer
231 views

Verification of a maximal antichain

In order theory, an antichain (Sperner family/clutter) is a subset of a partially-ordered set, with the property that no two elements are comparable with each other. A maximal antichain is the ...
0
votes
1answer
61 views

What are the complexity classes of these problems about divisibility and coprimality?

The problems 'Given $0<a<b$ and a prime $p<a$ is there an integer $\ell\in[a,b]$ such that $p|\ell$?' 'Given $0<a<b$ and an integer $q\not\in[a,b]$ is there an integer $\ell\in[a,b]$ ...
4
votes
0answers
191 views

What is the complexity class of this problem without Cramer's conjecture?

The problem 'Given $0<a<b$ is there a prime in the interval $[a,b]$?' is in $\mathsf{NP}$. If we assume Cramer's conjecture the problem is in $\mathsf{P}$ since if $b-a>(\log a)^{2+\epsilon}$ ...
0
votes
0answers
18 views

Properties of shortest-adjacent-edges forests

Given a finite symmetric graph $G(V,E), V=\lbrace 1,\dots,\,n\rbrace, E\subseteq \lbrace\lbrace u, v \rbrace\,|\, u,v\in V\rbrace$ with unique edge weights $\omega: E\ni e\mapsto \mathbb{R},\, \omega(...
0
votes
1answer
167 views

Maximize sum of edge weights on spanning tree

Problem: Given a complete graph with n vertices, the edge weight between vertex $i$ and vertex $j$ is $b[i]\times b[j]$. Under the condition that the degree of point $i$ on spanning tree is DEG $[i]$, ...
3
votes
0answers
180 views

How to solve special Diophantine equation systems (which one can solve by hand) with the computer?

I have a quadratic Diophantine equation system which is possibly not homogeneous and has some mixed and some linear terms. But I know that there are only finitely many solutions over the integers. One ...
2
votes
0answers
95 views

Evidence of optimality of sieve algorithms

Sieve techniques apply to integer factoring and discrete logarithm to provide $2^{O(((\log n)(\log\log n)^2)^{1/3})}$ complexity for $n$ bit factoring and $n$ bit prime discrete logarithm. The state ...
3
votes
0answers
88 views

Applications of products of random matrices

I'm studying the paper "Matrix concentration for products" and I'm trying to find simple applications of the inequalities for the expected value of the spectral norm of products of random ...
1
vote
0answers
62 views

Integer factorization given modular square root of 2

Let $N$ be composite. It is well-known that if $x^2 \equiv 1 \pmod N$, and $x \neq \pm 1 \pmod N$, then a factor of $N$ is easily found by computing gcd($N$, $x + 1$). I'm curious if there is a ...

1
2 3 4 5
27