Preemptive and non-preemptive generalized min sum set cover

DOI10.1007/s10107-013-0651-2zbMath1358.68321OpenAlexW2160834479MaRDI QIDQ2248757

Sungjin Im, Ruben van der Zwaan, M. I. Sviridenko

Publication date: 27 June 2014

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2012/3399/

zbMATH Keywords

approximationlatencyset coverpreemptionaverage cover time

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (2)

Adaptive Submodular Ranking and Routing ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on the generalized min-sum set cover problem
• Geometric algorithms and combinatorial optimization.
• On chromatic sums and distributed resource allocation
• On the approximability of average completion time scheduling under precedence constraints.
• A matched approximation bound for the sum of a greedy coloring
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Approximating min sum set cover
• Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
• A projected gradient algorithm for solving the maxcut SDP relaxation
• Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• A (2+ε)-approximation algorithm for the generalized preemptive open shop problem with minsum objective
• Optimal Long Code Test with One Free Bit
• Multiple intents re-ranking

This page was built for publication: Preemptive and non-preemptive generalized min sum set cover