Scheduling Split Intervals
From MaRDI portal
Publication:5470743
DOI10.1137/S0097539703437843zbMath1111.68046MaRDI QIDQ5470743
Joseph (Seffi) Naor, Irina Shapira, Magnús M. Halldórsson, Hadas Shachnai, Reuven Bar Yehuda
Publication date: 1 June 2006
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)
Related Items (43)
On edge intersection graphs of paths with 2 bends ⋮ Parameterized Complexity in Multiple-Interval Graphs: Domination ⋮ Recognizing \(d\)-interval graphs and \(d\)-track interval graphs ⋮ An \(O^*(1.4366^n)\)-time exact algorithm for maximum \(P_2\)-packing in cubic graphs ⋮ Generalized Hypergraph Matching via Iterated Packing and Local Ratio ⋮ The fullerene graphs with a perfect star packing ⋮ Dealing with several parameterized problems by random methods ⋮ Online scheduling of car-sharing request pairs between two locations ⋮ On independent set in \(B_1\)-EPG graphs ⋮ On the parameterized complexity of some optimization problems related to multiple-interval graphs ⋮ Online selection of intervals and \(t\)-intervals ⋮ Hardness and approximation for L-EPG and \(B_1\)-EPG graphs ⋮ Temporal interval cliques and independent sets ⋮ Optimization problems in dotted interval graphs ⋮ Interval scheduling and colorful independent sets ⋮ Partial multicovering and the \(d\)-consecutive ones property ⋮ Three ways to cover a graph ⋮ On streaming algorithms for geometric independent set and clique ⋮ Winner determination in geometrical combinatorial auctions ⋮ Maximal strip recovery problem with gaps: hardness and approximation algorithms ⋮ Exact and approximation algorithms for the complementary maximal strip recovery problem ⋮ An improved approximation algorithm for the complementary maximal strip recovery problem ⋮ Scheduling split intervals with non-uniform demands ⋮ Approximation algorithms for intersection graphs ⋮ Computing inductive vertex orderings ⋮ An Improved Approximation Algorithm for the Complementary Maximal Strip Recovery Problem ⋮ Iterative Packing for Demand and Hypergraph Matching ⋮ On Tree-Constrained Matchings and Generalizations ⋮ Maximizing Throughput in Flow Shop Real-Time Scheduling ⋮ Competitive algorithms for multistage online scheduling ⋮ Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy ⋮ Optimization problems in multiple subtree graphs ⋮ On tree-constrained matchings and generalizations ⋮ Inapproximability of maximal strip recovery ⋮ Minimum vertex cover in rectangle graphs ⋮ On linear and semidefinite programming relaxations for hypergraph matching ⋮ Parameterized complexity of two-interval pattern problem ⋮ A Retrospective on Genomic Preprocessing for Comparative Genomics ⋮ On recovering syntenic blocks from comparative maps ⋮ On Recovering Syntenic Blocks from Comparative Maps ⋮ Interval scheduling with economies of scale ⋮ The maximum clique problem in multiple interval graphs ⋮ Fast Diameter Computation within Split Graphs
This page was built for publication: Scheduling Split Intervals
