Title: The Weak Discrepancy of a Partially Ordered Set

Speaker: Ann Trenk

Abstract: In this talk, we discuss criteria for assigning integer ranks to elements of a partially ordered set. As an application, a manager may have a partial order of employees based on their performance and needs to assign an integer (salary level) to each employee. The following definitions make this more precise.

Given a poset $P = (X, \prec)$, and a non-negative integer k, a function $f: X \to Z$ is a k-ranking function of P if it satisfies the following conditions: (i) If $x \prec y$ in P then f(x) < f(y), and (ii) If $x \parallel y$ in P then $\vert f(x) - f(y)\vert \le k$ (where $\parallel$ denotes incomparability).

The weak discrepancy of a poset P (denoted wd(P)) is the minimum k for which there exists a k-ranking function of P. In our example, using a k-ranking function with k = wd(P) will assign salary levels to employees in a way that minimizes the maximum discrepancy between incomparable employees.

Our results include polynomial-time algorithms for finding wd(P) and for constructing a k-ranking function of P when $k \ge wk(P)$.