The algorithms tag has no wiki summary.
3
votes
1answer
50 views
Finding the vertices of a convex polyhedron from a set of planes
I'm new to computational geometry and advanced mathematics in general here so bear with me. I've spent a decent amount of time attempting to figure out this problem and I just can't find a solution.
...
2
votes
2answers
89 views
Reference Request: Representing Positive Integers as Differences with Minimal Hamming Weight
Background of my reference request is an observation that I made, while I was still in school: there are two ways to calculate $x*999$: either do it directly, by applying the multiplication algorithm ...
1
vote
0answers
15 views
In what paper was the shrinkage parameter introduced to the nelder-mead simplex direct search algorithm?
I have read lots of papers referencing a 4th shrinkage parameter when talking about the Nelder Mead Simplex method. However, I cannot see any shrinkage parameter in the flow chart of the original ...
24
votes
3answers
687 views
Are surjectivity and injectivity of polynomial functions from $\mathbb{Q}^n$ to $\mathbb{Q}$ algorithmically decidable?
Is there an algorithm which, given a polynomial $f \in \mathbb{Q}[x_1, \dots, x_n]$,
decides whether the mapping $f: \mathbb{Q}^n \rightarrow \mathbb{Q}$ is surjective,
respectively, injective? --
And ...
0
votes
0answers
38 views
A minimization problem [migrated]
Define $$L(w,u)=\frac{1}{2}\|w-u\|^2+\beta \|\frac{w}{x}\|,~w,u\in R^n$$
where $$\frac{w}{x}=(\frac{w_1}{x_1},\dots, \frac{w_n}{x_n})$$
$$\|x\|=\sqrt{x_1^2+\cdots+x_n^2}$$
Given $u$, $x$ and $\beta$, ...
2
votes
2answers
71 views
Reference Request for: Finding Large Bipartite Subgraphs via Destruction of Odd Cycles in Graphs
From the observation, that a bipartite graph doesn't contain odd cycles, it would seem natural to attempt to destroy all odd cycles in the most efficient way, by either removing edges or vertices of ...
0
votes
0answers
30 views
what is a flow in the context of the ford-fulkerson algorithm? [migrated]
I am learning about the Ford Fulkerson algorithm, but having a hard time getting an intuitive feel for what a "flow" is. Is the "flow" the amount that travels between two adjacent nodes on a graph? Or ...
3
votes
1answer
45 views
Practical error-estimates for (adaptive) Newton-Cotes Quadrature
I am looking for practical error estimates for Newton-Cotes Quadrature rules.
Most books on numerical methods I have found mainly deal with theoretical error bounds/estimates for the respective ...
8
votes
2answers
110 views
Covering convex polygons with inscribed disks
The following problem came up when discussing mapping software (e.g., Google maps) with computer scientists. By $B(c,r)$ I mean the planar disk (open or closed, it doesn't matter) of radius $r$ around ...
3
votes
0answers
44 views
On understanding Discrete-Valued Stochastic Processes( time series, panel data )
It seems to me that a significant proportion of work in probability theory, statistics and machine learning are on understanding continuous-valued, relatively weakly dependent, or linear dependent ...
4
votes
1answer
89 views
Algorithm to detect if an element of a (commutative) ring is in a subring?
For rings finitely-generated over a field, the theory of Groebner bases gives us quite an efficient algorithm for determining whether an element of the ring is in a given ideal of the ring.
Is there ...
7
votes
1answer
240 views
Quickly finding optimal subset of pairs of numerator and denominator terms for special objective functions
Given a multi-set of pairs $((a_i,b_i))_{i \in Y}$ of positive numerator and denominator terms (i.e. each pair has one numerator term and one denominator term), my general problem is to find the ...
2
votes
0answers
94 views
Beating Kadane's Algorithm
I am seeking some reference on already existing work for the following problem.
Given an $n$-dimensional square matrix $A=DP$ where $D$ is a diagonal and $P$ is a permutation matrix (think of Gaussian ...
1
vote
1answer
63 views
computing $c_5$ in “Primality testing with Gaussian periods”
As far as I know, the April 2011 version of #143 on this page has not been improved upon.
On page 10 of that paper, the authors give an algorithm that uses a constant $\:c_{\hspace{.01 in}5}\:$.
...
1
vote
0answers
114 views
How many distinct pairwise difference multisets exists? [migrated]
For all $K$-point integer-valued sets whose elements are between $1$ and $N$ and also distinct, how many distinct pairwise difference multiset exists?
Note that the difference is evaluated modulu N.
...
