On min sum vertex cover and generalized min sum set cover
type: Item
instance of: scholarly article
title: On min sum vertex cover and generalized min sum set cover
author: N. Bansal
author: Jatin Batra
author: Majid Farhadi
author: Prasad Tetali
published in: SIAM Journal on Computing
publication date: 2025-01-14T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68W20
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68W40
Mathematics Subject Classification ID: 90C25
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 7966979
zbMATH Keywords: randomized algorithms
zbMATH Keywords: approximation algorithms
zbMATH Keywords: hardness of approximation
zbMATH Keywords: scheduling
zbMATH Keywords: convex programming
zbMATH Keywords: tails of probability distributions
MaRDI profile type: Publication
cites work: Multiple intents re-ranking
cites work: Q5417729
cites work: Optimal Long Code Test with One Free Bit
cites work: On chromatic sums and distributed resource allocation
cites work: A projected gradient algorithm for solving the maxcut SDP relaxation
cites work: Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
cites work: Q4471366
cites work: A threshold of ln n for approximating set cover
cites work: Q4411280
cites work: Approximating min sum set cover
cites work: On Submodular Search and Machine Scheduling
cites work: All-Norms and All-L_p-Norms Approximation Algorithms
cites work: Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
cites work: Algorithms – ESA 2005
cites work: On the Distribution of the Number of Successes in Independent Trials
cites work: Preemptive and non-preemptive generalized min sum set cover
cites work: Approximating Minimum Linear Ordering Problems
cites work: Monotone Convergence of Binomial Probabilities and a Generalization of Ramanujan's Equation
cites work: Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
cites work: Precedence-Constrained Min Sum Set Cover
cites work: Database Theory - ICDT 2005
cites work: The boundaries of submodular functions
cites work: A note on the generalized min-sum set cover problem
cites work: On the approximability of average completion time scheduling under precedence constraints.
DOI: 10.1137/21M1434052
description: scientific article; zbMATH DE number 7966979