Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree

DOI10.1007/s10878-009-9276-zzbMath1220.90146MaRDI QIDQ543514

Jesper Jansson, Yuichi Asahiro, Hirotaka Ono, Kouhei Zenmyo, Eiji Miyano

Publication date: 17 June 2011

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-009-9276-z

zbMATH Keywords

scheduling; approximation algorithm; degree; maximum flow; inapproximability; graph orientation

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C59: Approximation methods and heuristics in mathematical programming

Related Items

Unnamed Item, Unnamed Item, Graph orientation with splits, Makespan minimization on unrelated parallel machines with simple job-intersection structure and bounded job assignments, Graph Orientation with Edge Modifications, Degree-constrained graph orientation: maximum satisfaction and minimum violation, Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity, Restricted assignment scheduling with resource constraints, A 3/2-approximation algorithm for the graph balancing problem with two weights, Upper and lower degree-constrained graph orientation with minimum penalty, Makespan minimization on unrelated parallel machines with a few bags, Parameterized orientable deletion, Scheduling meets \(n\)-fold integer programming, Approximation algorithms for the graph balancing problem with two speeds and two job lengths, Graph balancing: a special case of scheduling unrelated parallel machines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for scheduling unrelated parallel machines
• Planar orientations with low out-degree and compaction of adjacency matrices
• A combinatorial theorem in plane geometry
• Combinatorial optimization in geometry
• Balanced vertex-orderings of graphs
• Polynomial time approximation algorithms for machine scheduling: Ten open problems
• Minimizing maximum indegree
• Beyond the flow decomposition barrier
• GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• A Faster Deterministic Maximum Flow Algorithm
• Complexity of approximating the oriented diameter of chordal graphs
• Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures
• Computing and Combinatorics