Partitioning a weighted partial order

DOI10.1007/s10878-007-9086-0zbMath1136.06003OpenAlexW2108883059MaRDI QIDQ927191

Linda S. Moonen, Frits C. R. Spieksma

Publication date: 4 June 2008

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://lirias.kuleuven.be/handle/123456789/122706

zbMATH Keywords

partially ordered setsapproximation algorithmschain decomposition

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Speedup the optimization of maximal closure of a node-weighted directed acyclic graph ⋮ On the online track assignment problem ⋮ Solution approaches for storage loading problems with stacking constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bounded vertex colorings of graphs
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• The hardness of approximation: Gap location
• Mutual exclusion scheduling
• The mutual exclusion scheduling problem for permutation and comparability graphs.
• Scheduling a batch processing machine with bipartite compatibility graphs
• Cardinality-restricted chains and antichains in partially ordered sets
• Batch processing with interval graph compatibilities between tasks
• A decomposition theorem for partially ordered sets
• Exact Algorithms for a Loading Problem with Bounded Clique Width
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
• Bounded vertex coloring of trees