Precedence-Constrained Min Sum Set Cover

DOI10.4230/LIPIcs.ISAAC.2017.55zbMath1457.68222OpenAlexW2777161377MaRDI QIDQ5136276

Julián Mestre, Anthony Wirth, Jessica McClintock

Publication date: 25 November 2020

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/8264/pdf/LIPIcs-ISAAC-2017-55.pdf/

zbMATH Keywords

precedence constrainedplanted dense subgraphmin sum set cover

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items

A General Framework for Approximating Min Sum Ordering Problems

Cites Work

• Unnamed Item
• Partially ordered knapsack and applications to scheduling
• On the hardness of approximating label-cover
• Approximating min sum set cover
• The knapsack problem with neighbour constraints
• Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
• Minimum Multicolored Subgraph Problem in Multiplex PCR Primer Set Selection and Population Haplotyping
• On Approximating Target Set Selection
• On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
• Scheduling Tasks with AND/OR Precedence Constraints
• Intractability of assembly sequencing: Unit disks in the plane
• Multiple intents re-ranking
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Database Theory - ICDT 2005
• Approximation and Online Algorithms