The fractional weak discrepancy of a partially ordered set

DOI10.1016/J.DAM.2007.05.032MaRDI QIDQ2457003zbMATH OpenOpenAlexFDO

Authors Alan Shuchat, Randy Shull, Ann Trenk

Publication date 29 October 2007

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://repository.wellesley.edu/scholarship/102

zbMATH Keywords

fractional weak discrepancypartially ordered set

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Linear programming (90C05)

Review text

The authors introduce the notion of the fractional weak discrepancy of a poset \(P = \left( {V, \prec } \right)\). They formulate the fractional weak discrepancy problem as a linear program and show how its solution can also be used to calculate the integral weak discrepancy. Further they interpret the dual linear program as a circulation problem in a related directed graph and use this to give a structural characterization of the fractional weak discrepancy of a poset.

Recommendations

• The total weak discrepancy of a partially ordered set
• Forbidden subposets for fractional weak discrepancy at most \(k\)
• Fractional weak discrepancy of posets and certain forbidden configurations
• Linear discrepancy and weak discrepancy of partially ordered sets
• Range of the fractional weak discrepancy function

Cites work

• Fractional weak discrepancy of posets and certain forbidden configurations
• scientific article; zbMATH DE number 3867330 (Why is no real title available?)
• scientific article; zbMATH DE number 3877239 (Why is no real title available?)
• Introduction to algorithms
• Linear discrepancy and weak discrepancy of partially ordered sets
• Network flows. Theory, algorithms, and applications.
• On k-weak orders: Recognition and a tolerance result
• On the Weakness of an Ordered Set
• Range of the fractional weak discrepancy function

Cited in

(12)

• Fractional weak discrepancy and interval orders
• Linear discrepancy and weak discrepancy of partially ordered sets
• Partial orderings with the weak Freese-Nation property
• Tolerance orders of open and closed unit intervals
• Range of the fractional weak discrepancy function
• A note on fragmentability and weak-\(G_{\delta }\) sets
• The total weak discrepancy of a partially ordered set
• On the Weakness of an Ordered Set
• The fractional weak discrepancy of \((M, 2)\)-free posets
• The \(t\)-discrepancy of a poset
• When linear and weak discrepancy are equal
• Forbidden subposets for fractional weak discrepancy at most \(k\)

Describes a project that uses

Uses Software

• LINDO
• LINGO

This page was built for publication: The fractional weak discrepancy of a partially ordered set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2457003)