Capacitated max-batching with interval graph compatibilities
DOI10.1016/j.tcs.2015.10.047zbMath1333.05246OpenAlexW2186826687MaRDI QIDQ899311
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
Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Signed and weighted graphs (05C22)
Related Items
Cites Work
- Unnamed Item
- Restrictions of graph partition problems. I
- On the max coloring problem
- Dynamic scheduling on a single batch processing machine with split compatibility graphs
- Batch processing with interval graph compatibilities between tasks
- A quasi-PTAS for unsplittable flow on line graphs
- Clique partitioning of interval graphs with submodular costs on the cliques
- Clique Clustering Yields a PTAS for max-Coloring Interval Graphs
- Max-coloring and online coloring with bandwidths on interval graphs
- Scheduling unit tasks to minimize the number of idle periods
- Approximation schemes for covering and packing problems in image processing and VLSI
- Scheduling Semiconductor Burn-In Operations to Minimize Total Flowtime
- Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs
- Data Aggregation in Sensor Networks: Balancing Communication and Delay Costs
- Latency Constrained Aggregation in Sensor Networks
- Automata, Languages and Programming