On Submodular Search and Machine Scheduling

DOI10.1287/MOOR.2018.0978MaRDI QIDQ5108249zbMATH OpenOpenAlexFDO

Authors Thomas Lidbetter, Robbert Fokkink, László A. Végh

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

zbMATH Keywords

game theoryschedulingsearch gamessubmodular functions

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Search theory (90B40) Games involving graphs (91A43)

Abstract: Suppose some objects are hidden in a finite set $S$ of hiding places which must be examined one-by-one. The cost of searching subsets of $S$ is given by a submodular function and the probability that all objects are contained in a subset is given by a supermodular function. We seek an ordering of $S$ that finds all the objects in minimal expected cost. This problem is NP-hard and we give an efficient combinatorial $2$-approximation algorithm, generalizing analogous results in scheduling theory. We also give a new scheduling application $1|prec|sum{w}_{A}h(C_A)$, where a set of jobs must be ordered subject to precedence constraints to minimize the weighted sum of some concave function $h$ of the completion times of {em subsets} of jobs. We go on to give better approximations for submodular functions with low {em total curvature} and we give a full solution when the problem is what we call {em series-parallel decomposable}. Next, we consider a zero-sum game between a cost-maximizing Hider and a cost-minimizing Searcher. We prove that the equilibrium mixed strategies for the Hider are in the base polyhedron of the cost function, suitably scaled, and we solve the game in the series-parallel decomposable case, giving approximately optimal strategies in other cases.

Recommendations

• A Review for Submodular Optimization on Machine Scheduling Problems
• Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times
• SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES BY SUBMODULAR OPTIMIZATION
• Approximation algorithms for the multiprocessor scheduling with submodular penalties
• scientific article; zbMATH DE number 3922372
• Application of submodular optimization to single machine scheduling with controllable processing times subject to release dates and deadlines
• A submodular optimization approach to bicriteria scheduling problems with controllable processing times on parallel machines
• Algorithms for single machine scheduling problem with release dates and submodular penalties
• Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties
• Handling scheduling problems with controllable parameters by methods of submodular optimization

Cites work

• A Dynamic Programming Approach to Sequencing Problems
• A Fast Parametric Submodular Intersection Algorithm for Strong Map Sequences
• A fully combinatorial 2-approximation algorithm for precedence-constrained scheduling a single machine to minimize average weighted completion time
• A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
• A Periodic Optimal Search
• Alternating search at two locations
• Approximating Minimum Linear Ordering Problems
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Complexity of searching an immobile hider in a graph
• Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs
• Decomposition of submodular functions
• Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
• Dual techniques for scheduling on a machine with varying speed
• scientific article; zbMATH DE number 5888315 (Why is no real title available?)
• scientific article; zbMATH DE number 3126094 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• Increasing speed scheduling and flow scheduling
• Min-sum scheduling under precedence constraints
• Minimizing symmetric submodular functions
• Mining coal or finding terrorists: the expanding search paradigm
• Multi-armed bandit allocation indices. With a foreword by Peter Whittle.
• On the approximability of single-machine scheduling with precedence constraints
• On the performance of Smith's rule in single-machine scheduling with nonlinear cost
• Optimal Long Code Test with One Free Bit
• Optimal Sequencing by Modular Decomposition: Polynomial Algorithms
• Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Scheduling to minimize total weighted completion time: performance guarantees of LP-based heuristics and lower bounds
• Scheduling under dynamic speed-scaling for minimizing weighted completion time and energy consumption
• Search games
• Search games with multiple hidden objects
• Searching a variable speed network
• Selfish load balancing
• Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
• Sequencing with Series-Parallel Precedence Constraints
• Single Machine Job Sequencing with Precedence Constraints
• Single machine precedence constrained scheduling is a Vertex cover problem
• Single-Machine Scheduling with Precedence Constraints
• Submodular functions and optimization.
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• The boundaries of submodular functions
• The complexity of searching a graph
• The local-global conjecture for scheduling with non-linear cost
• The theory of search games and rendezvous.

Cited in

(12)

• Applying ``peeling onion approach for competitive analysis in online scheduling with rejection
• Search and delivery man problems: when are depth-first paths optimal?
• Search and rescue in the face of uncertain threats
• Time-critical testing and search problems
• A Review for Submodular Optimization on Machine Scheduling Problems
• A semi-online algorithm for single machine scheduling with rejection
• Exact and Approximation Algorithms for the Expanding Search Problem
• A General Framework for Approximating Min Sum Ordering Problems
• Optimal patrolling strategies for trees and complete networks
• Hardness and approximation of submodular minimum linear ordering problems
• On min sum vertex cover and generalized min sum set cover
• Scheduling search procedures: The wheel of fortune

This page was built for publication: On Submodular Search and Machine Scheduling

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