Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree

DOI10.1007/S10878-009-9276-ZzbMath1220.90146OpenAlexW2119344260MaRDI 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

schedulingapproximation algorithmdegreemaximum flowinapproximabilitygraph orientation

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (16)

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

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

This page was built for publication: Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree