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)
schedulingconvex programmingapproximation algorithmsrandomized algorithmshardness of approximationtails of probability distributions
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)