Faster Algorithms for Semi-Matching Problems
From MaRDI portal
Publication:2799478
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
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
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