Posted on

#StackBounty: #algorithms #strings #string-metrics #edit-distance Edit distance of list with unique elements

Bounty: 50

Levenshtein-Distance edit distance between lists
is a well studied problem.
But I can’t find much on possible improvements if
it is known that no element does occurs more than once in each list.

Let’s also assume that the elements are comparable/sortable
(but the lists to compare are not sorted to begin with).

In particular I am interested
if the uniqueness of elements makes it possible to improve upon
Ukkonen’s algorithm for edit distance
which has time complexity $O(min(m,n)s)$ and
space complexity $O(min(s,m,n)s)$,
where $s$ is the minimum cost of the editing steps.

More formally,

how efficiently can we compute the edit distance between two given strings
$s,t in Sigma^*$
with the promise that they don’t have any repeated letters?

$Sigma$ is a very large alphabet.

Get this bounty!!!

Posted on

#StackBounty: #algorithms #expectation-maximization #t-distribution #latent-variable EM for a form of Student distribution

Bounty: 50

I consider $n$ replications from the following sampling density function for $y_iinBbb{R}^p$

begin{align}
f_p(y_ivertmu,Sigma,nu)={displaystyle {frac {Gamma left[(nu +p)/2right]}{Gamma (nu /2)nu ^{d/2}pi ^{p/2}left|{boldsymbol {Sigma }}right|^{1/2}}}left[1+{frac {1}{nu }}({mathbf {y} }-{boldsymbol {beta x_i }})^{T}{boldsymbol {Sigma }}^{-1}({mathbf {y} }-{boldsymbol {beta x_i }})right]^{-(nu +p)/2}}label{eq:2}
end{align}

Where $beta$ is unknown and the matrix $Sigma$ is parametrized as $sigma^2 Q.$

I would like to perform an EM algorithm.

If I am not mistaken, we have for the log-likelikehood
$$log L(Psi)=frac{-1}{2}nplog(2pi)-frac1{2}nlog vert Sigmavert-frac1{2sigma^2}sum_{j=1}^n z_j(y_j-beta x_i)^TQ^{-1}(y_j-beta x_i)$$

where I forgot everything about $nu$ because it supposed to be known.

Now we have

$$Zvert Y=ysim Gamma(m_1,m_2)$$ with $m_1=frac{1}{2}(nu+p)$ et $m_2=frac{1}{2}(nu+(y-mu)^TSigma(y-mu))$ for general $t_p(mu,Sigma,nu)$ distribution.

If I am doing the chameleon we have

$$Zvert Y=ysim Gamma(m_1,m_2)$$ with $m_1=frac{1}{2}(nu+p)$ et $m_2=frac{1}{2sigma^2}(nu+(y-mu_i)^T Q^{-1}(y-mu_i))$

In general case we have
begin{equation}
E_{Psi^{(k)}}(Z_jvert y_j)=frac{nu+p}{nu+Q(y_j,mu^{(k)},Sigma^{(k)})}
end{equation}

I can also do the chameleon here but I am pretty sure I miss something otherwise is trivial.

What am I missing ?

Get this bounty!!!

Posted on

#StackBounty: #algorithms #computability #logic #search-problem Is there an analysis of the creation of axioms for a mathematical struc…

Bounty: 100

Historically, what has happened is the following:

  1. There is a “mechanical” structure, most importantly, arithmetic, which operates according to a set of well-defined rules that a stupid computer can easily follow. e.g. a computer can easily calculate $5349cdot 5345=…$

  2. There is a “mechanical” proof-system, most importantly, first order logic, which also operates according to well-defined rules that a stupid computer can follow. e.g. a computer can easily apply derivation rules to go from $forall x phi(x)$ to $exists x phi(x)$, etc.

  3. Then there is a non-mechanical “creative” human, who uses his badly-understood “natural insight” to formulate a set of “axioms about arithmetic”, which are words in (2)’s language “about” the operations of (1)’s arithmetic computations. He also formulates a set of “logical axioms”, the rules by which the mechanical proof system should operate. He chooses these rules because his intuitive insight says that they are “obviously correct”.

It seems to me that this third element in the chain (though it happens first chronologically), is always done in an ad-hoc way. But the fact that this has always been done this way so far, doesn’t mean that it necessarily has to be this way.

My question is: Has there been an analysis of the creation of axioms as a computational problem? That is, of the problem of choosing axioms about some mathematical structure, for use in a logic-language?

This computational problem is essentially: given e.g. the rules of arithmetic, find a first-order statement that we can use as an axiom to then derive further properties.

ps. I know that this is a vague question. I am simply asking whether someone has analysed this problem in some way.

Get this bounty!!!

Posted on

#StackBounty: #algorithms #optimization #linear-programming #convex-hull How to find the supremum of all the "good" (interior…

Bounty: 50

Let $S subset mathbf{R}^3$ be a set of point and let $O=(x_0,y_0,z_0)$ be the origin/point of reference.

We consider a convex polytope $P$ good / interior if:

  1. $P$ is wholly contained within the interior of the convex hull of $S$:
    $P subsetneq text{convexhull}(S)$.

  2. $O$ is contained within the interior of $P$, namely: $O in P$.

  3. none of the points in $S$ are in $P$ namely $S cap P = emptyset$.

Out of all good convex polytopes, we want to find either the maximum (supremum) of their volumes, i.e., $sup text{Vol}(P)$ where $P$ ranges over good polytopes.

Here is a 2D modest illustration (the green polytope might not be really the optimal):

example

The black dots are the set $S$, the origin $O$ is in the middle. The red lines go through the points in $S$ which define the boundary of $S$ (not a good polytope) and the green lines go through a good polytope.

Is there an efficient algorithm to compute this best convex and non-convex polytopes for a given set $S$ of points and origin $O$?

I would like to formulate this problem as an optimization problem or to come up with some algorithm using triangulation, $alpha$-shapes or $beta$-skeleton geometric transformation + convex hull, linear programming, maybe working in the dual space? etc.

One idea which I have is “pumping down” the convex hull of Delaunay Triangulation:

DT $leftarrow$ delaunayTriangulation($S cup O$)

CH $leftarrow$ convexHull(DT)

while Not empty(DT) and $O notin CH$:

$quad$ i. previousDT $leftarrow$ DT

$quad$ ii. update DT $leftarrow$ DT $setminus$ CH

return previousDT

EDIT: I think what I am looking for in a one-liner of math symbols is:

$$text{argmax}_{P} text{text{Vol}(P) , | , O in P setminus partial P , ; ,
Scap P = emptyset , ; , P subsetneq text{convexhull}(S) } $$

Where $partial P$ is the boundary of a polytope $P$.

Get this bounty!!!

Posted on

#StackBounty: #algorithms #complexity-theory #linear-programming #convex-hull How to find the supremum of all the "good" (int…

Bounty: 50

Let $S subset mathbf{R}^3$ be a set of point and let $O=(x_0,y_0,z_0)$ be the origin/point of reference.

We consider a convex polytope $P$ good / interior if:

  1. $P$ is wholly contained within the interior of the convex hull of $S$:
    $P subsetneq text{convexhull}(S)$.

  2. $O$ is contained within the interior of $P$, namely: $O in P$.

  3. none of the points in $S$ are in $P$ namely $S cap P = emptyset$.

Out of all good convex polytopes, we want to find either the maximum (supremum) of their volumes, i.e., $sup text{Vol}(P)$ where $P$ ranges over good polytopes.

Here is a 2D modest illustration (the green polytope might not be really the optimal):

example

The black dots are the set $S$, the origin $O$ is in the middle. The red lines go through the points in $S$ which define the boundary of $S$ (not a good polytope) and the green lines go through a good polytope.

Is there an efficient algorithm to compute this best convex and non-convex polytopes for a given set $S$ of points and origin $O$?

I would like to formulate this problem as an optimization problem or to come up with some algorithm using triangulation, $alpha$-shapes or $beta$-skeleton geometric transformation + convex hull, linear programming, maybe working in the dual space? etc.

One idea which I have is “pumping down” the convex hull of Delaunay Triangulation:

DT $leftarrow$ delaunayTriangulation($S cup O$)

CH $leftarrow$ convexHull(DT)

while Not empty(DT) and $O notin CH$:

$quad$ i. previousDT $leftarrow$ DT

$quad$ ii. update DT $leftarrow$ DT $setminus$ CH

return previousDT

EDIT: I think what I am looking for in a one-liner of math symbols is:

$$text{argmax}_{P} text{text{Vol}(P) , | , O in P setminus partial P , ; ,
Scap P = emptyset , ; , P subsetneq text{convexhull}(S) } $$

Where $partial P$ is the boundary of a polytope $P$.

Get this bounty!!!

Posted on

#StackBounty: #algorithms #graphs #graph-theory #data-structures Graph algorithm or framework for determining node affinity based on ut…

Bounty: 50

I’m looking for an algorithm or framework for thinking about how to determine affinities between nodes. Perhaps affinity is poor choice of wording, but basically I want to use utilities between nodes to determine how alike or unalike they are from each other. I’ve attached an example diagram to illustrate what I mean:

enter image description here

In this example, Entities A and B are not well-aligned due to the negative utility between them. An appropriate algorithm or framework should identify that they belong to different groups, clusters, etc.

Additionally, I should be able to infer that Entities B and C are likely to be well-aligned, due to the mutual misalignment with A.

The utility magnitudes should also reflect the degree of alignment or misalignment. For example A2 and B3 should more more misaligned than A1 and B3.

To complicate things further, the utility “units” may be different, with multiple edges between nodes. As a simplifying assumption, I may be able to normalize utilities into a single edge and unit.

I apologize if this question is vague and/or ill-suited for this StackExchange. However I really don’t have a good lead on how to tackle such a problem.

Get this bounty!!!

Posted on

#StackBounty: #algorithms #complexity-theory #linear-programming #convex-hull How to find the supremum of all the "good" poly…

Bounty: 50

Let $S subset mathbf{R}^3$ be a set of point and let $O=(x_0,y_0,z_0)$ be the origin/point of reference.

We consider a convex polytope $P$ good / interior if:

  1. $P$ is wholly contained within the interior of the convex hull of $S$:
    $P subsetneq text{convexhull}(S)$.

  2. $O$ is contained within the interior of $P$, namely: $O in P$.

  3. none of the points in $S$ are in $P$ namely $S cap P = emptyset$.

Out of all good convex polytopes, we want to find either the maximum (supremum) of their volumes, i.e., $sup text{Vol}(P)$ where $P$ ranges over good polytopes.

Here is a 2D modest illustration (the green polytope might not be really the optimal):

example

The black dots are the set $S$, the origin $O$ is in the middle. The red lines go through the points in $S$ which define the boundary of $S$ (not a good polytope) and the green lines go through a good polytope.

Is there an efficient algorithm to compute this best convex and non-convex polytopes for a given set $S$ of points and origin $O$?

I would like to formulate this problem as an optimization problem or to come up with some algorithm using triangulation, $alpha$-shapes or $beta$-skeleton geometric transformation + convex hull, linear programming, maybe working in the dual space? etc.

One idea which I have is “pumping down” the convex hull of Delaunay Triangulation:

DT $leftarrow$ delaunayTriangulation($S cup O$)

CH $leftarrow$ convexHull(DT)

while Not empty(DT) and $O notin CH$:

$quad$ i. previousDT $leftarrow$ DT

$quad$ ii. update DT $leftarrow$ DT $setminus$ CH

return previousDT

EDIT: I think what I am looking for in a one-liner of math symbols is:

$$text{argmax}_{P} text{text{Vol}(P) , | , O in P setminus partial P , ; ,
Scap P = emptyset , ; , P subsetneq text{convexhull}(S) } $$

Where $partial P$ is the boundary of a polytope $P$.

Get this bounty!!!

Posted on

#StackBounty: #algorithms #complexity-theory #linear-programming #convex-hull How to find the supremum of polytopes which are interior …

Bounty: 50

Let $S subset mathbf{R}^3$ be a set of point and let $O=(x_0,y_0,z_0)$ be the origin/point of reference.

We consider a convex polytope $P$ good / interior if:

  1. $P$ is wholly contained within the interior of the convex hull of $S$:
    $P subsetneq text{convexhull}(S)$.

  2. $O$ is contained within the interior of $P$, namely: $O in P$.

  3. none of the points in $S$ are in $P$ namely $S cap P = emptyset$.

Out of all good convex polytopes, we want to find either the maximum (supremum) of their volumes, i.e., $sup text{Vol}(P)$ where $P$ ranges over good polytopes.

Here is a 2D modest illustration (the green polytope might not be really the optimal):

example

The black dots are the set $S$, the origin $O$ is in the middle. The red lines go through the points in $S$ which define the boundary of $S$ (not a good polytope) and the green lines go through a good polytope.

Is there an efficient algorithm to compute this best convex and non-convex polytopes for a given set $S$ of points and origin $O$?

I would like to formulate this problem as an optimization problem or to come up with some algorithm using triangulation, $alpha$-shapes or $beta$-skeleton geometric transformation + convex hull, linear programming, maybe working in the dual space? etc.

One idea which I have is “pumping down” the convex hull of Delaunay Triangulation:

DT $leftarrow$ delaunayTriangulation($S cup O$)

CH $leftarrow$ convexHull(DT)

while Not empty(DT) and $O notin CH$:

$quad$ i. previousDT $leftarrow$ DT

$quad$ ii. update DT $leftarrow$ DT $setminus$ CH

return previousDT

EDIT: I think what I am looking for in a one-liner of math symbols is:

$$text{argmax}_{P} text{text{Vol}(P) , | , O in P setminus partial P , ; ,
Scap P = emptyset , ; , P subsetneq text{convexhull}(S) } $$

Where $partial P$ is the boundary of a polytope $P$.

Get this bounty!!!

Posted on

#StackBounty: #algorithms #complexity-theory #linear-programming #convex-hull How to find the supermum of polytopes which are interior …

Bounty: 50

Let $S subset mathbf{R}^3$ be a set of point and let $O=(x_0,y_0,z_0)$ be the origin/point of reference.

We consider a convex polytope $P$ good / interior if:

  1. $P$ is wholly contained within the interior of the convex hull of $S$:
    $P subsetneq text{convexhull}(S)$.

  2. $O$ is contained within the interior of $P$, namely: $O in P$.

  3. none of the points in $S$ are in $P$ namely $S cap P = emptyset$.

Out of all good convex polytopes, we want to find either the maximum (supremum) of their volumes, i.e., $sup text{Vol}(P)$ where $P$ ranges over good polytopes.

Here is a 2D modest illustration (the green polytope might not be really the optimal):

example

The black dots are the set $S$, the origin $O$ is in the middle. The red lines go through the points in $S$ which define the boundary of $S$ (not a good polytope) and the green lines go through a good polytope.

Is there an efficient algorithm to compute this best convex and non-convex polytopes for a given set $S$ of points and origin $O$?

I would like to formulate this problem as an optimization problem or to come up with some algorithm using triangulation, $alpha$-shapes or $beta$-skeleton geometric transformation + convex hull, linear programming etc.

One idea which I have is “pumping down” the convex hull of Delaunay Triangulation:

DT $leftarrow$ delaunayTriangulation($S cup O$)

CH $leftarrow$ convexHull(DT)

while Not empty(DT) and $O notin CH$:

$quad$ i. previousDT $leftarrow$ DT

$quad$ ii. update DT $leftarrow$ DT $setminus$ CH

return previousDT

EDIT: I think what I am looking for in a one-liner of math symbols is:

$$text{argmax}_{P} text{text{Vol}(P) , | , O in P setminus partial P , ; ,
Scap P = emptyset , ; , P subsetneq text{convexhull}(S) } $$

Where $partial P$ is the boundary of a polytope $P$.

Get this bounty!!!

Posted on

#StackBounty: #algorithms #complexity-theory #linear-programming #convex-hull How to find the supermum of the polytopes which are inter…

Bounty: 50

Let $S subset mathbf{R}^3$ be a set of point and let $O=(x_0,y_0,z_0)$ be the origin/point of reference.

We consider a convex polytope $P$ good / interior if:

  1. $P$ is wholly contained within the interior of the convex hull of $S$:
    $P subsetneq text{convexhull}(S)$.

  2. $O$ is contained within the interior of $P$, namely: $O in P$.

  3. none of the points in $S$ are in $P$ namely $S cap P = emptyset$.

Out of all good convex polytopes, we want to find either the maximum (supremum) of their volumes, i.e., $sup text{Vol}(P)$ where $P$ ranges over good polytopes.

Here is a 2D modest illustration (the green polytope might not be really the optimal):

example

The black dots are the set $S$, the origin $O$ is in the middle. The red lines go through the points in $S$ which define the boundary of $S$ (not a good polytope) and the green lines go through a good polytope.

Is there an efficient algorithm to compute this best convex and non-convex polytopes for a given set $S$ of points and origin $O$?

I would like to formulate this problem as an optimization problem or to come up with some algorithm using triangulation, $alpha$-shapes or $beta$-skeleton geometric transformation + convex hull, linear programming etc.

One idea which I have is “pumping down” the convex hull of Delaunay Triangulation:

DT $leftarrow$ delaunayTriangulation($S cup O$)

CH $leftarrow$ convexHull(DT)

while Not empty(DT) and $O notin CH$:

$quad$ i. previousDT $leftarrow$ DT

$quad$ ii. update DT $leftarrow$ DT $setminus$ CH

return previousDT

EDIT: I think what I am looking for in a one-liner of math symbols is:

$$text{argmax}_{P} text{text{Vol}(P) , | , O in P setminus partial P , ; ,
Scap P = emptyset , ; , P subsetneq text{convexhull}(S) } $$

Where $partial P$ is the boundary of a polytope $P$.

Get this bounty!!!