Semi-matchings for bipartite graphs and load balancing

DOI10.1016/j.jalgor.2005.01.003zbMath1100.68079OpenAlexW2052924791MaRDI QIDQ5491460

Nicholas J. A. Harvey, László Lovász, Richard E. Ladner, Tami Tamir

Publication date: 5 October 2006

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jalgor.2005.01.003

zbMATH Keywords

bipartite graphsload balancingmatching algorithmsoptimal algorithmssemi-matching

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Deterministic scheduling theory in operations research (90B35) 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)

Related Items

Scheduling High Multiplicity Jobs on Parallel Multi-Purpose Machines with Setup Times and Machine Available Times, Parallel machine scheduling with nested processing set restrictions, On computing an optimal semi-matching, Solving the at-most-once problem with nearly optimal effectiveness, The minimum maximal k-partial-matching problem, Wake up and join me! An energy-efficient algorithm for maximal matching in radio networks, A Survey of the Generalized Assignment Problem and Its Applications, A generalization of Hungarian method and Hall's theorem with applications in wireless sensor networks, Literal Selection in Switching Lattice Design, Efficient algorithms for scheduling equal-length jobs with processing set restrictions on uniform parallel batch machines, Matching with sizes (or scheduling with processing set restrictions), Matching with sizes (or scheduling with processing set restrictions), Scheduling unit length jobs on parallel machines with lookahead information, Scheduling Algorithms for Tree-Based Data Collection in Wireless Sensor Networks, Distributed backup placement in networks, Online scheduling of two job types on a set of multipurpose machines with unit processing times, Algorithms for storage allocation based on client preferences, Multipurpose machine scheduling with rejection and identical job processing times, Faster Algorithms for Semi-Matching Problems, The existence of universally agreed fairest semi-matchings in any given bipartite graph, On the distributed complexity of the semi-matching problem, Brief Announcement: Distributed Approximations for the Semi-matching Problem, Online Collaborative Filtering on Graphs, Density decompositions of networks, On Computing an Optimal Semi-matching, Decreasing minimization on M-convex sets: background and structures, Decreasing minimization on M-convex sets: algorithms and applications, Decreasing minimization on base-polyhedra: relation between discrete and continuous cases