Scheduling with Precedence Constraints of Low Fractional Dimension

No abstract is available for this paper.

• Publication year

  2007

• Venue

  Conference on Integer Programming and Combinatorial Optimization

• Publication date

  2007-06-25

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/978-3-540-72792-7_11
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Single Machine Precedence Constrained Scheduling Is a Vertex Cover Problem

  2009influential reference
• Partially ordered knapsack and applications to scheduling

  2007cited by this paper
• Algorithms - ESA 2006, 14th Annual European Symposium, Zurich, Switzerland, September 11-13, 2006, Proceedings

  2006cited by this paper
• Approximating Precedence-Constrained Single Machine Scheduling by Coloring

  2006influential reference
• Single-Machine Scheduling with Precedence Constraints

  2005influential reference
• Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem

  2003cited by this paper
• A fully combinatorial 2-approximation algorithm for precedence-constrained scheduling a single machine to minimize average weighted completion time

  2003cited by this paper
• Algorithms — ESA 2002

  2002cited by this paper
• On the approximability of average completion time scheduling under precedence constraints

  2001influential reference
• Some APX-completeness results for cubic graphs

  2000cited by this paper
• Dimension, Graph and Hypergraph Coloring

  2000influential reference
• Precedence Constrained Scheduling to Minimize Sum of Weighted Completion Times on a Single Machine

  1999cited by this paper
• Polynomial time approximation algorithms for machine scheduling: ten open problems

  1999cited by this paper
• A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine

  1999influential reference
• Proof of claims

  1997cited by this paper
• Fractional Graph Theory: A Rational Approach to the Theory of Graphs

  1997cited by this paper
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms

  1997cited by this paper
• Scheduling to Minimize Total Weighted Completion Time: Performance Guarantees of LP-Based Heuristics and Lower Bounds

  1996cited by this paper
• Scheduling to minimize average completion time: off-line and on-line algorithms

  1996cited by this paper
• On the 2-Chain Subgraph Cover and Related Problems

  1994cited by this paper
• On the fractional dimension of partially ordered sets

  1994influential reference
• Fractional dimension of partial orders

  1992influential reference
• Combinatorics and Partially Ordered Sets: Dimension Theory

  1992cited by this paper
• Computationally Tractable Classes of Ordered Sets

  1989cited by this paper
• Algorithms and Order

  1988cited by this paper
• Efficient bounds for the stable set, vertex cover and set packing problems

  1983cited by this paper
• Scheduling Interval-Ordered Tasks

  1979cited by this paper
• Complexity of Scheduling under Precedence Constraints

  1978cited by this paper
• The Dimension of Semiorders

  1978cited by this paper
• Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints

  1978influential reference
• Fractional Graph Theory

  1978cited by this paper
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey

  1977cited by this paper
• Some Simplified NP-Complete Graph Problems

  1976influential reference
• Vertex packings: Structural properties and algorithms

  1975influential reference
• Properties of vertex packing and independence system polyhedra

  1974influential reference
• Minimal scrambling sets of simple orders

  1972cited by this paper

• Minimals Plus: An improved algorithm for the random generation of linear extensions of partially ordered sets

  2019cites this paper
• An exact algorithm for the precedence-constrained single-machine scheduling problem

  2013cites this paper
• Considering the game-theoretic approach and ultra combinative costs on scheduling

  2013cites this paper
• Online Privacy: Towards Informational Self-Determination on the Internet

  2013cites this paper
• The Feedback Arc Set Problem with Triangle Inequality Is a Vertex Cover Problem

  2011cites this paper
• Vertex cover in graphs with locally few colors

  2011influential citation
• On the Approximability of Single-Machine Scheduling with Precedence Constraints

  2011cites this paper
• Hardness of Precedence Constrained Scheduling on Identical Machines

  2011cites this paper
• Approximability of Precedence Constrained and Robust Scheduling Problems

  2010cites this paper
• Conditional hardness of precedence constrained scheduling on identical machines

  2010cites this paper
• Single Machine Precedence Constrained Scheduling Is a Vertex Cover Problem

  2009cites this paper
• Approximability of some classical graph and scheduling problems

  2009cites this paper
• Algorithmic and game-theoretic perspectives on scheduling

  2008cites this paper
• P C S  C  D T  P O

  2008influential citation
• Precedence Constraint Scheduling and Connections to Dimension Theory of Partial Orders

  2008cites this paper
• Inapproximability Results for Sparsest Cut, Optimal Linear Arrangement, and Precedence Constrained Scheduling

  2007cites this paper
• Testing for Concise Representations

  2007cites this paper
• Single Machine Precedence Constrained Scheduling Is a Vertex Cover Problem

  2006cites this paper
• Packing and Scheduling Algorithms for Information and Communication Services Creative Commons By-nc-nd 3.0 Unported License

  year unknowncites this paper