#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!!!

#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!!!

#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!!!

#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!!!

#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!!!

#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!!!

#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!!!

#StackBounty: #algorithms #graphs #network-flow How to use flow network in order to find optimal task scheduling for two processors (mi…

Bounty: 50

We’re given two computers connected by some network connection and we want to perform $n$ tasks. For each task $1le i le n$ we’re given the time $a_i$ it will take to complete it on computer $a$ and the time $b_i$ it will take to complete it on computer $b$. Some tasks depend on other tasks completion therefore we’re given time $c_{i,j}$ which is needed in case tasks $i,j$ are performed on different computers. The overall time to complete all tasks is defined as sum of times that tasks will run on computers $a,b$ and communication times $c_{i,j}$.

For example, if there’re 3 tasks and we perform tasks $1$ and $3$ on computer $a$ while task $2$ is performed on computer $b$ then the overall time will be: $(a_1+a_2) + b_2 + (c_{1,2} + c_{2,3})$. What could be the algorithm using flow network to find optimal tasks scheduling such that the overall time were minimal?

I’m not sure how to build the flow network which corresponds to the problem. It seems like this is a min-cost flow problem but I’m not sure and if it is I’m wondering how Ford-Fulkerson can be applied here because it finds max flow.


Get this bounty!!!

#StackBounty: #algorithms #graphs #partial-order How to convert a dependency graph to series-parallel representation?

Bounty: 50

I’m given a finite partial order, in the form of a dependency graph between items, and I’d like to have it in series-parallel form (Wikipedia).

So formally, given a finite partial order $le$ on a set $V$, I’d like to construct it using only the following rules:

  • For every item $P$ in $V$, we have the partial order on ${P}$.
  • Series. If we have orders $X$ and $Y$, then we also have $X;Y$, which adds both orders such that additionally for any $x,y in X,Y$ we have $x le y$.
  • Parallel. If we have orders $X$ and $Y$, then we also have $X + Y$, which adds both orders such that any $x,y in X,Y$ are incomparable ($x notle y land y notle x$).

What kind of algorithm could I use to construct this SP-form?

(I’m aware that the graph is required to be “N-free” for an SP-form to exist.)

For a larger graph which is regularly updated, it would be helpful if the algorithm were incremental, but I have no idea whether that would be possible.

Examples. Writing $P$ for the partial order on the single-element set ${P}$, a linear order would look like $A;B;C;…$ (all in sequence). The “unorder”, where different items are incomparable, would look like $A+B+C+…$ (all in parallel). A binary tree could look like $A;((B;(C+D))+(E;(F+G)))$.

Background. In a task list or issue tracking application which allows you to specify dependencies between tasks or issues, it seems helpful to present them in a series-parallel form, instead of the usual flat list which at most is topologically sorted.


Get this bounty!!!