A General Framework for Approximating Min Sum Ordering Problems

DOI10.1287/IJOC.2021.1124MaRDI QIDQ5087715zbMATH OpenOpenAlexFDO

Authors Felix Happach, Thomas Lidbetter, Lisa Hellerstein

Publication date 1 July 2022

Published in INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2004.05954

zbMATH Keywords

approximation algorithmsBoolean function evaluationmin sum set coverschedulingsearch theory

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Recommendations

• scientific article; zbMATH DE number 1947050
• Approximating Minimum Linear Ordering Problems
• Approximating min sum set cover
• A note on the generalized min-sum set cover problem
• A constant factor approximation algorithm for generalized MIN-sum set cover

Cites work

• A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
• Approximating min sum set cover
• Approximating Minimum Linear Ordering Problems
• Approximation algorithms for stochastic submodular set cover with applications to Boolean function evaluation and min-knapsack
• Approximation and Online Algorithms
• Database Theory - ICDT 2005
• Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs
• Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
• Finding optimal satisficing strategies for and-or trees
• scientific article; zbMATH DE number 1947050 (Why is no real title available?)
• Minimum Color Sum of Bipartite Graphs
• Mining coal or finding terrorists: the expanding search paradigm
• Multiple intents re-ranking
• On chromatic sums and distributed resource allocation
• On Submodular Search and Machine Scheduling
• On the complexity of scheduling unit-time jobs with or-precedence constraints
• Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
• Precedence-Constrained Min Sum Set Cover
• Precedence-constrained scheduling and min-sum set cover (extended Abstract)
• Query strategies for priced information (extended abstract)
• Scheduling Tasks with AND/OR Precedence Constraints
• Scheduling to minimize total weighted completion time: performance guarantees of LP-based heuristics and lower bounds
• Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
• Sequencing unreliable jobs on parallel machines
• Sequential testing of complex systems: a review
• Single machine precedence constrained scheduling is a Vertex cover problem
• Single-Machine Job Sequencing with Treelike Precedence Ordering and Linear Delay Penalties
• Single-Machine Scheduling with Precedence Constraints
• The boundaries of submodular functions
• The search value of a set
• The stochastic score classification problem

Cited in

(6)

• Minimax approach to the construction of a generalized ordering
• Network construction/restoration problems: cycles and complexity
• Approximating Minimum Linear Ordering Problems
• scientific article; zbMATH DE number 5556488 (Why is no real title available?)
• scientific article; zbMATH DE number 1303559 (Why is no real title available?)
• Adaptivity gaps for the stochastic Boolean function evaluation problem

This page was built for publication: A General Framework for Approximating Min Sum Ordering Problems

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