# Tagged Questions

The tag has no wiki summary.

113 views

### Does any one know what this problem is called? [on hold]

We are given finite sets A and B and a set S⊆P(A). The members of S may have arbitrary intersections with one another and their union is not necessarily A. We wish to determine whether there is a ...
106 views

### how to solve 3 6-degree polynomial equations for 3 variables? [on hold]

I am a physicist and need to solve three $6$-order polynomial equations for $3$ unknowns $(p, q, r)$. Here is the system of equations looks like: $$\sum(A[n]*p^i*q^j*r^k) = 0,$$ ...
70 views

### how to reduce 3-colorable graph to this? [on hold]

suppose we have a finite set X and a set S of subsets of X and we want to determine is there a subset S' of S such that all members of X belong to exactly one set in S' I think the best problem to ...
84 views

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

There is certain Eratosthenes spirit to my problem (See below). First of all I'd like to stress the mathematical aspect of my question. Also, my question does not amount to the divide and conquer ...
71 views

### independent subset problems [on hold]

I'm interested in the following which i suspect is probably a well studied problem. Given a set $N=\{1,2,...,n\}$ and $M=\{1,2,...,m\}$ consider a map $$f:N\rightarrow 2^{M}$$ (elements of $N$ to ...
137 views

### Decomposing representations of finite groups of Lie type via computer

This is related to my previous question here. Let me remind you what that question asked: Let $\text{St}_n(\mathbb{F}_q)$ be the Steinberg module (over $\mathbb{C}$) for ...
54 views

### Intersection graphs

Does anybody know of a paper which proves that finding the maximum independent set in geometric intersection graphs is NP hard? Even general intersection graphs?
106 views

### Explicitly showing that a free group is LERF [closed]

Let $F$ be a free group on a finite set $X$, and let $M$ be a finitely generated subgroup. Marshall Hall's theorem states that $M$ is closed in the profinite topology on $F$. That is, $M$ is the ...
213 views

### Algorithm to produce random number with a gamma distribution

I'd like to produce pseudo-random numbers with different distributions for a Monte Carlo simulation. I've got the poisson distribution working nicely with an algorithm from Knuth. I'm having trouble ...
43 views

### Trilateration issues, when circles don't intersect

I'm working on Indoor localization where I've deployed multiple iBeacons in my environment. I'm taking distances from all the beacons through their RSSI values. They are not 100% accurate though. Now ...
68 views

### Using upper bound information in graph search

I am using A* (A-Star) to search a graph. A* algorithm takes advantage of the information $h(x)$, which is a lower bound of the distance between a vertex $x$ and the destination vertex. In other ...
117 views

### DL-problem on abelian variety

Let $A$ be an abelian variety over $\mathbb{F_q}$ with dimension $n$. Let $q$ be a constant. Is there polynomial algorithm of finding discrete logarithm in $A$? UPD: really I don't undestend: can we ...
201 views

### Find all faces in a graph from list of edges

I have the information from a undirected graph stored in a 2D array. The array stores all of the edges between nodes, e.g. graph[3] might be equal to [1,8,30] and represents the fact that node 3 ...
143 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 ...
102 views

### Minimize distance between centroids of subsets of points

In a n-dimensional space, I want to divide a set of m points into v (non-empty) subsets. I want to minimize the sum of the pairwise Euclidean distances between the centroids of the resulting subsets. ...
137 views

### Polygamous stable marriage/ assignment problem

I'm not sure under which 'algorithm' it falls under, but here is the problem: I need to match each person to 5 people from the opposite gender (each guy gets 5 girls, each girl gets 5 guys). Not all ...
96 views

### Existence of subgraphs when given its degree sequence

For a given simple graph $G$ with $n$ vertices $v_1,v_2,\dots v_n$, the corresponding degree sequence is $d_1,d_2,\cdots,d_n$. My qusetion is: How to determine whether there exist subgraphs in $G$ ...
175 views

The problem Let $G=(V,E)$ be a graph. $k = O\left(\log(|V|)\right)$ distinct vertices are picked randomly from $V$. We call the set of chosen $k$ vertices $T$. Assumptions about the graph: You may ...
158 views

### What is God's number for the WrapSlide puzzle?

WrapSlide is a slide-puzzle (reminding of Rubik's Cube) consisting of a 6x6 grid of coloured tiles which are separated into four quadrants of 3x3 tiles. When it is unmixed all the tiles in a quadrant ...
295 views

### Does a classification of simultaneous conjugacy classes in a product of symmetric groups exist?

Let the symmetric group $S_n$ on $n$ letters act on $S_n^d=S_n\times\cdots\times S_n$ by simultaneous conjugation, i.e. $\pi\in S_n$ acts on $(\sigma_1,\ldots,\sigma_d)\in S_n^d$ by ...
45 views

### Is there an efficient algorithm for sampling from the negative hypergeometric distribution? [closed]

I'm writing a small statistics library currently. One of the algorithms I'm implementing has two variants: one that samples the hypergeometric distribution and one that samples the negative ...
67 views

### Containing a “fuzzy” ellipsoid within an ordinary ellipsoid

Consider the ellipsoid described by the inequality $(x - x_c)^T P^{-1} (x - x_c) \leq 1$, where the vector $x_c \in \mathbb{R}^n$ denotes the center of the ellipsoid and the symmetric positive ...
120 views

### Combinatorial optimization problem involving infinite spin system

In material science research, I am developing an algorithm to solve an infinite combinatorial optimization problem which I believe is the most natural problem when the system size goes to infinity. ...
100 views

### enumeration of connected blocks in finite size square

Given a square of size n by m, how many ways could we choose sites, such that all the sites are connected? By "connected" we mean "connected" by adjacent sites. We will illustrate by example, say, we ...
43 views

### Complexity of an algorithm to solve linear diophantine equations

A friend of mine ask me yesterday a problem, however, the interesting part for me it is not his problem, but what I will ask here. I want to know the optimal complexity of an algorithm (I mean the ...
137 views

### Modular polynomials for elliptic curves point counting

The Schoof-Elkies-Atkin (SEA) algorithm (for counting points on elliptic curves over a finite field) performs computations over polynomials modulo some modular polynomials. Originally the "classical" ...
68 views

### Paper on unit disk graphs

I was wondering if anybody knows of a 'link' to the paper by Marathe 1995 et al on analysis of the greedy algorithm for finding a Max independent set in Unit Disk Graphs?
63 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 ...