Skip to main content
Computer Science

Return to Question

Tweeted twitter.com/StackCompSci/status/723378121903239170
deleted 5 characters in body; edited tags
Source Link
D.W. ♦
D.W. ♦
  • 165.6k
  • 21
  • 230
  • 490

Maximize function over a a set with a transitive and antisymmetric relation

Let $\mathcal{R}$ be a transitive and antisymmetric relation defined over a finite set $X$.

For any set $S\subseteq X$ letdefine $\Gamma(S)=\left\{y\in S ,\not \exists x\in S \mid (x,y)\in\mathcal{R}\right\}$$\Gamma(S)=\left\{y\in S \mid \not \exists x\in S . (x,y)\in\mathcal{R}\right\}$. (Thus,  $y \in \Gamma(S)$ if it belongs to $S$ and no other element in $S$ "dominates" it.)

Suppose that each element is assigned a weight. This is represented by the function $w:X\to \mathbb{R}^+$.

The problem is to find a subset $S \subseteq X$ to maximize $\sum_{z \in \Gamma(S)}w(z)$.

Is this problem polynomial-time solvable?

Thanks.

Maximize function over a a set with a transitive and antisymmetric relation

Let $\mathcal{R}$ be a transitive and antisymmetric relation defined over a finite set $X$.

For any set $S\subseteq X$ let $\Gamma(S)=\left\{y\in S ,\not \exists x\in S \mid (x,y)\in\mathcal{R}\right\}$. (Thus,$y \in \Gamma(S)$ if it belongs to $S$ and no other element in $S$ "dominates" it.)

Suppose that each element is assigned a weight. This is represented by the function $w:X\to \mathbb{R}^+$.

The problem is to find a subset $S \subseteq X$ to maximize $\sum_{z \in \Gamma(S)}w(z)$.

Is this problem polynomial-time solvable?

Thanks.

Maximize function over a set with a transitive and antisymmetric relation

Let $\mathcal{R}$ be a transitive and antisymmetric relation defined over a finite set $X$.

For any set $S\subseteq X$ define $\Gamma(S)=\left\{y\in S \mid \not \exists x\in S . (x,y)\in\mathcal{R}\right\}$. (Thus,  $y \in \Gamma(S)$ if it belongs to $S$ and no other element in $S$ "dominates" it.)

Suppose that each element is assigned a weight. This is represented by the function $w:X\to \mathbb{R}^+$.

The problem is to find a subset $S \subseteq X$ to maximize $\sum_{z \in \Gamma(S)}w(z)$.

Is this problem polynomial-time solvable?

Source Link
ALVARO ALEXIS FLORES
ALVARO ALEXIS FLORES
  • 53
  • 4

Maximize function over a a set with a transitive and antisymmetric relation

Let $\mathcal{R}$ be a transitive and antisymmetric relation defined over a finite set $X$.

For any set $S\subseteq X$ let $\Gamma(S)=\left\{y\in S ,\not \exists x\in S \mid (x,y)\in\mathcal{R}\right\}$. (Thus,$y \in \Gamma(S)$ if it belongs to $S$ and no other element in $S$ "dominates" it.)

Suppose that each element is assigned a weight. This is represented by the function $w:X\to \mathbb{R}^+$.

The problem is to find a subset $S \subseteq X$ to maximize $\sum_{z \in \Gamma(S)}w(z)$.

Is this problem polynomial-time solvable?

Thanks.