Capacitated max-batching with interval graph compatibilities

DOI10.1016/J.TCS.2015.10.047MaRDI QIDQ899311zbMATH OpenOpenAlexFDO

Authors Tim Nonner

Publication date 28 December 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.10.047

zbMATH Keywords

approximation algorithmsapproximation schemesschedulingNP-hardness

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Capacitated max-batching with interval graph compatibilities
• Batch processing with interval graph compatibilities between tasks
• Parallel maximum matching algorithms in interval graphs
• Parallel algorithms for maximum matching in complements of interval graphs and related problems
• Scheduling a batch processing machine with bipartite compatibility graphs
• Online algorithms for scheduling on batch processing machines with interval graph compatibilities between jobs
• Scheduling on a batch processing machine with split compatibility graphs
• Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds
• On the solution of a graph partitioning problem under capacity constraints
• Optimal parallel time bounds for the maximum clique problem on intervals

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A quasi-PTAS for unsplittable flow on line graphs
• Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs
• Approximation schemes for covering and packing problems in image processing and VLSI
• Automata, Languages and Programming
• Batch processing with interval graph compatibilities between tasks
• Clique Clustering Yields a PTAS for max-Coloring Interval Graphs
• Clique partitioning of interval graphs with submodular costs on the cliques
• Data Aggregation in Sensor Networks: Balancing Communication and Delay Costs
• Dynamic scheduling on a single batch processing machine with split compatibility graphs
• Latency Constrained Aggregation in Sensor Networks
• Max-coloring and online coloring with bandwidths on interval graphs
• On the max coloring problem
• Restrictions of graph partition problems. I
• Scheduling Semiconductor Burn-In Operations to Minimize Total Flowtime
• Scheduling unit tasks to minimize the number of idle periods

Cited in

(2)

• Capacitated max-batching with interval graph compatibilities
• Clique clustering yields a PTAS for max-coloring interval graphs

This page was built for publication: Capacitated max-batching with interval graph compatibilities

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