On min sum vertex cover and generalized min sum set cover

DOI10.1137/21M1434052MaRDI QIDQ6663094

Prasad Tetali, N. Bansal, Jatin Batra, Majid Farhadi

Publication date: 14 January 2025

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

schedulingconvex programmingapproximation algorithmsrandomized algorithmshardness of approximationtails of probability distributions

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Convex programming (90C25) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Combinatorial probability (60C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Randomized algorithms (68W20)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A note on the generalized min-sum set cover problem
• The boundaries of submodular functions
• On chromatic sums and distributed resource allocation
• On the approximability of average completion time scheduling under precedence constraints.
• Approximating min sum set cover
• Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
• Preemptive and non-preemptive generalized min sum set cover
• A projected gradient algorithm for solving the maxcut SDP relaxation
• A threshold of ln n for approximating set cover
• All-Norms and All-L_p-Norms Approximation Algorithms
• Approximating Minimum Linear Ordering Problems
• On the Distribution of the Number of Successes in Independent Trials
• Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• On Submodular Search and Machine Scheduling
• Precedence-Constrained Min Sum Set Cover
• Optimal Long Code Test with One Free Bit
• Multiple intents re-ranking
• Database Theory - ICDT 2005
• Algorithms – ESA 2005
• Monotone Convergence of Binomial Probabilities and a Generalization of Ramanujan's Equation

This page was built for publication: On min sum vertex cover and generalized min sum set cover

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