On Submodular Search and Machine Scheduling
From MaRDI portal
Publication:5108249
DOI10.1287/moor.2018.0978zbMath1437.91103arXiv1607.07598OpenAlexW2965775701MaRDI QIDQ5108249
Thomas F. Lidbetter, László A. Végh, Robbert J. Fokkink
Publication date: 30 April 2020
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1607.07598
Search theory (90B40) Games involving graphs (91A43) Deterministic scheduling theory in operations research (90B35)
Related Items (9)
Exact and Approximation Algorithms for the Expanding Search Problem ⋮ A General Framework for Approximating Min Sum Ordering Problems ⋮ Search and delivery man problems: when are depth-first paths optimal? ⋮ Search and rescue in the face of uncertain threats ⋮ Optimal patrolling strategies for trees and complete networks ⋮ A Review for Submodular Optimization on Machine Scheduling Problems ⋮ Time-critical testing and search problems ⋮ Applying ``peeling onion approach for competitive analysis in online scheduling with rejection ⋮ A Semi-Online Algorithm for Single Machine Scheduling with Rejection
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Scheduling under dynamic speed-scaling for minimizing weighted completion time and energy consumption
- Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
- Single machine precedence constrained scheduling is a Vertex cover problem
- Decomposition of submodular functions
- Search games
- Minimizing symmetric submodular functions
- The boundaries of submodular functions
- Complexity of searching an immobile hider in a graph
- A fully combinatorial 2-approximation algorithm for precedence-constrained scheduling a single machine to minimize average weighted completion time
- The theory of search games and rendezvous.
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- 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
- The local-global conjecture for scheduling with non-linear cost
- Submodular functions and optimization.
- Search Games with Multiple Hidden Objects
- On the Approximability of Single-Machine Scheduling with Precedence Constraints
- Increasing Speed Scheduling and Flow Scheduling
- Multi‐Armed Bandit Allocation Indices
- Approximating Minimum Linear Ordering Problems
- Dual Techniques for Scheduling on a Machine with Varying Speed
- A Dynamic Programming Approach to Sequencing Problems
- Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
- Optimal Sequencing by Modular Decomposition: Polynomial Algorithms
- The complexity of searching a graph
- Sequencing with Series-Parallel Precedence Constraints
- Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs
- Single Machine Job Sequencing with Precedence Constraints
- Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
- Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
- A Fast Parametric Submodular Intersection Algorithm for Strong Map Sequences
- Min-Sum Scheduling Under Precedence Constraints
- Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds
- On the Performance of Smith’s Rule in Single-Machine Scheduling with Nonlinear Cost
- Optimal Long Code Test with One Free Bit
- Searching a Variable Speed Network
- Mining Coal or Finding Terrorists: The Expanding Search Paradigm
- A Periodic Optimal Search
- Single-Machine Scheduling with Precedence Constraints
- Alternating search at two locations
This page was built for publication: On Submodular Search and Machine Scheduling
