Faster Algorithms for Semi-Matching Problems

DOI10.1145/2601071zbMath1333.05288arXiv1004.3363OpenAlexW2033561606MaRDI QIDQ2799478

Jittat Fakcharoenphol, Danupon Nanongkai, Bundit Laekhanukit

Publication date: 11 April 2016

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1004.3363

zbMATH Keywords

schedulingcombinatorial optimizationsemi-matchingdesign and analysis of algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items

On computing an optimal semi-matching, Distributed backup placement in networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A generalization of Hungarian method and Hall's theorem with applications in wireless sensor networks
• Scheduling jobs with equal processing times subject to machine eligibility constraints
• An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs
• Selfish load balancing and atomic congestion games
• Algorithms for storage allocation based on client preferences
• Parallel machine scheduling of machine-dependent jobs with unit-length.
• An efficient retrieval selection algorithm for video servers with random duplicated assignment storage technique.
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A survey of game-theoretic approaches in wireless sensor networks
• Scheduling unit-length jobs with machine eligibility restrictions
• An Even Faster and More Unifying Algorithm for Comparing Trees via Unbalanced Bipartite Matchings
• An Algorithm for a Minimum Cover of a Graph
• Algebraic Algorithms for Matching and Matroid Problems
• Faster Algorithms for Semi-matching Problems (Extended Abstract)
• The Balanced Edge Cover Problem
• Analysis of the Q.A.D. algorithm for an homogeneous multiprocessor computing model with independent memories
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Network Flow and Testing Graph Connectivity
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Faster Scaling Algorithms for Network Problems
• Scheduling independent tasks to reduce mean finishing time
• Least Majorized Elements and Generalized Polymatroids
• Semi-matchings for bipartite graphs and load balancing
• On some techniques useful for solution of transportation network problems
• Technical Note—Minimizing Average Flow Time with Parallel Machines