A General Framework for Approximating Min Sum Ordering Problems
From MaRDI portal
Publication:5087715
DOI10.1287/ijoc.2021.1124OpenAlexW3015680468MaRDI QIDQ5087715
Felix Happach, Thomas F. 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
Related Items
Network construction/restoration problems: cycles and complexity, Adaptivity gaps for the stochastic Boolean function evaluation problem
Cites Work
- Unnamed Item
- Unnamed Item
- On the complexity of scheduling unit-time jobs with or-precedence constraints
- Sequencing unreliable jobs on parallel machines
- Single machine precedence constrained scheduling is a Vertex cover problem
- The boundaries of submodular functions
- On chromatic sums and distributed resource allocation
- The search value of a set
- Sequential testing of complex systems: a review
- Approximating min sum set cover
- Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
- A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
- Precedence-constrained scheduling and min-sum set cover (extended Abstract)
- Finding optimal satisficing strategies for and-or trees
- Approximating Minimum Linear Ordering Problems
- Query strategies for priced information (extended abstract)
- Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
- Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs
- Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
- Minimum Color Sum of Bipartite Graphs
- Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds
- Scheduling Tasks with AND/OR Precedence Constraints
- Approximation Algorithms for Stochastic Submodular Set Cover with Applications to Boolean Function Evaluation and Min-Knapsack
- On Submodular Search and Machine Scheduling
- Precedence-Constrained Min Sum Set Cover
- Multiple intents re-ranking
- Mining Coal or Finding Terrorists: The Expanding Search Paradigm
- Database Theory - ICDT 2005
- Single-Machine Scheduling with Precedence Constraints
- Single-Machine Job Sequencing with Treelike Precedence Ordering and Linear Delay Penalties
- Approximation and Online Algorithms
