Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14245
For citation please use:
Main Title: Base Polytopes of Series-Parallel Posets: Linear Description and Optimization
Author(s): Schrader, Rainer
Schulz, Andreas S.
Wambach, Georg
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15472
http://dx.doi.org/10.14279/depositonce-14245
License: http://rightsstatements.org/vocab/InC/1.0/
Abstract: We define the base polytope B(P,g) of a partially ordered set P and a supermodular function g on the ideals of P as the convex hull of the incidence vectors of all linear extensions of P. This new class of polytopes contains, among others, the base polytopes of supermodular systems and permutahedra as special cases. After introducing the notion of compatibility for g, we give a complete linear description of B(P,g) for series-parallel posets and compatible functions g. In addition, we describe a greedy-type procedure which exhibits Sidney's job sequencing algorithm to minimize the total weighted completion time as a natural extension of the matroidal greedy algorithm from sets to posets.
Subject(s): base polytope
poset
set
scheduling
Issue Date: 1996
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 1996, 535
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Report-535-1996.pdf
Format: Adobe PDF | Size: 10.67 MB
DownloadShow Preview
Thumbnail
Report-535-1996.ps
Format: Postscript | Size: 212.9 kB
Download

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.