Minimum-weight partitioning of a set with associated subsets

2022/12/12 by Yakov Zinder, Bertrand M.T. Lin, Zinder, Yakov +3
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #Digital Image Processing Techniques #Embedded Systems Design Techniques #FOS: Computer and information sciences #Scheduling and Optimization Algorithms

paper · pdf · doi:10.48550/arxiv.2212.05823

openalex publication_date 2022/12/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The paper presents complexity results and performance guaranties for a family of approximation algorithms for an optimisation problem arising in software testing and manufacturing. The problem is formulated as a partitioning of a set where each element has an associated subset in another set, but can also be viewed as a scheduling problem with infinitely large communication delay, precedence constraints in the form of a bipartite graph, and duplication.

Related

• Efficient Locally Optimal Number Set Partitioning for Scheduling,\n Allocation and Fair Selection
• A (2 + ε)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective
• Minimum size generating partitions and their application to demand fulfillment optimization problems
• Descent With Approximate Multipliers is Enough: Generalising Max-Weight
• Approximation Ratio of LD Algorithm for Multi-Processor Scheduling and the Coffman-Sethi Conjecture