Preemptive and non-preemptive generalized min sum set cover

DOI10.1007/S10107-013-0651-2MaRDI QIDQ2248757zbMATH OpenOpenAlexFDO

Authors Sungjin Im, Ruben van der Zwaan, Maxim 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

approximationpreemptionset coverlatencyaverage 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)

Recommendations

• Preemptive and non-preemptive generalized min sum set cover
• scientific article; zbMATH DE number 1947050
• The geometry of scheduling
• Approximating min sum set cover
• A note on the generalized min-sum set cover problem

Cites work

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

Cited in

(8)

• Preemptive and non-preemptive generalized min sum set cover
• Precedence-Constrained Min Sum Set Cover
• Approximating min sum set cover
• A constant factor approximation algorithm for generalized MIN-sum set cover
• Hardness and approximation of submodular minimum linear ordering problems
• Matroid coflow scheduling
• Adaptive submodular ranking and routing
• On min sum vertex cover and generalized min sum set cover

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2248757)