Explore chapters and articles related to this topic
Matchings in graphs
Published in V. K. Balakrishnan, Network Optimization, 2019
If G = (V, E) is an arbitrary undirected graph in which each edge e has a nonnegative weight w(e), then the maximum weight matching problem is the problem of finding a matching M such that the sum of the weights of the edges in M is as large as possible. The maximum cardinality matching problem is obviously a special case of this problem when each edge is assigned a weight equal to 1.
Atm Switch Architecture and Systems
Published in Naoaki Yamanaka, High-Performance Backbone Network Technology, 2020
A number of algorithms exist to solve the dynamic matching optimally, either as a maximum size matching (MSM) or a maximum weight matching (MWM) [12]. MSM finds the maximum number of input-output connections. MWM maximizes the weight sum of the match. It has been shown that 100% throughput can be achieved for all admissible i.i.d. arrivals [3] with MWM and wi,o = qi,o (LQF).
Buffer Merging Algorithms
Published in Praveen K. Murthy, Shuvra S. Bhattacharyya, Memory Management for Synthesis of DSP Software, 2018
Praveen K. Murthy, Shuvra S. Bhattacharyya
A matching M is a set of edges such that no two edges in M share an endpoint. The weight of a matching is the sum of the weights of the edges in the matching. A maximum weight matching is a matching of maximum weight. Maximum weight matchings in bipartite graphs can be found in polynomial time ( 0(| 2. log (| ))); for example, using the "Hungarian" algorithm [3050
Web service discovery with incorporation of web services clustering
Published in International Journal of Computers and Applications, 2023
Sunita Jalal, Dharmendra Kumar Yadav, Chetan Singh Negi
The Hungarian method [23] can be used to obtain a solution for assignment problem in polynomial time. In our approach, we use the Hungarian method to obtain a match between inputs/outputs in the requested query and inputs/outputs in the web service description. Our goal for input matching is to assign each input in the requested query to exactly one input in service description while maximizing total matching score. The same goal is for output matching. The problem of input and output matching can be viewed in terms of finding maximum weight matching in the bipartite graph. In our case, the bipartite graph is complete. The complete bipartite graph for representing the problem of input matching contains two disjoint set of vertices. Vertices of one set denote input parameters of the requested query and vertices of another set denote input parameters of an operation described in a web service description. Each vertex of one set is connected to all vertices of another set and each edge between two vertices is labeled with semantic similarity score between them.
Practical taxi sharing schemes at large transport terminals
Published in Transportmetrica B: Transport Dynamics, 2019
Zhiyuan Liu, Shuaian Wang, Kai Huang, Jun Chen, Yingna Fu
We give a sketch of the idea of how [P1] is solved in polynomial time based on Schrijver (2003). The maximum weight matching problem is equivalent to the maximum weight perfect matching problem. The convex hull of all of the feasible solutions to the maximum weight perfect matching problem can be explicitly defined by a set of constraints, the number of which is exponential. However, there is a strongly polynomial time algorithm that can check whether a point satisfies all of the constraints, and if the answer is no, output a violated constraint. Thus the separation oracle is polynomially solvable. The equivalence between optimization and separation via the ellipsoid method leads to a polynomial time algorithm for the maximum weight matching problem.
A general system for heuristic minimization of convex functions over non-convex sets
Published in Optimization Methods and Software, 2018
S. Diamond, R. Takapoui, S. Boyd
Projecting (with ) onto the set of assignment matrices involves choosing an entry from each column of Z such that no two chosen entries are from the same row and the sum of chosen entries is maximized. Assuming that the entries of Z are the weights of edges in a bipartite graph, the projection onto the set of assignment matrices will be equivalent to finding a maximum-weight matching in a bipartite graph. The Hungarian method [52] is a well-known polynomial time algorithm to find the maximum weight matching, and hence also the projection onto assignment matrices.