Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 20 for “"Weighted matching"”.
-
Algorithms for Vertex-Weighted Matching in Graphs
A matching M in a graph is a subset of edges such that no two edges in M are incident on the same vertex. Matching is a fundamental combinatorial problem that has applications in many contexts: high-performance computing, bioinformatics, network switch design, web technologies, etc. Examples in the …
-
Improving group role assignment problem by incremental assignment algorithm
… a basic combinatorial optimization problem. In a weighted bipartite graph, the Assignment Problem is to find a largest sum of weights matching. The Hungarian method is a well-known algorithm which is combinatorial optimization. Adding a new row and a new column to a weighted bipartite graph is …
-
Musings on matchings, matrices, and multiplicities
… G, that contains cycles, the construction of the weighted matching polynomial and its many properties are derived. These properties are shown to determine a relationship between the multiplicities of the roots of the weighted matching polynomial and the graph operation of vertex deletion in G, …
-
Approximating Properties of Data Streams
… consider the problem of estimating the maximum weighted matching of a graph whose edges are revealed in a streaming fashion. We develop a reduction from the maximum weighted matching problem to the maximum cardinality matching problem that only doubles the approximation factor of a streaming …
-
Matchings with a size constraint
We study the matching problem and some variants such as b-matching and (g, f)-factors. This thesis aims at polynomial algorithms which in addition have other properties. In particular, we develop a polynomial algorithm which can find optimal solutions of each possible size for weighted matching …
-
Processing graphs and intervals in the sliding window model
… problems in the sliding window model: Maximum Weighted Matching and Interval<br/>Selection.<br/>We provide the following results, which are presented in the works [ADKN23] and<br/>[AK24]:<br/>1. We improve upon the previous results of Maximum Weighted Matching in the sliding window model. Using …
-
Asset Volatility and Wealth Transfers: Evidence from Stock Repurchase Announcements
… for bondholders. Traditional rating matching introduces: (i) an upward bias, particularly pronounced with smaller illiquid bonds, in estimating abnormal bond returns; and (ii) failure in identifying negative significance due to the reliance on size-weighted matching index returns. …
-
An Exploration of the Matching Polynomial
The matching polynomial for graphs was defined by Farrell in a paper published in 1979 as an invariant for graphs with fixed edge and vertex weights. However, the same polynomial had been modeled before and since by scientists in other disciplines; in particular, the matching polynomial models …
-
Multilevel Methods for Sparsification and Linear Arrangement Problems on Networks
… We are pushing the boundaries of fast maximum weighted matching algorithms for coarsening schemes on graphs by introducing novel ideas for asymmetric coupling between coarse and fine variables of the problem.
-
Exploring Efficiency in Split Federated Learning under System Heterogeneity: A Study of System Synchronization and Resource Optimization
… pairing, modeled as a deferred-acceptance-based weighted matching game that aligns local utilities with global objectives. Extensive experiments on VGG-16 using the Tiny-ImageNet dataset under non-IID data partitions demonstrate that CSFL significantly reduces training latency and energy …
-
Physical design of area-array integrated circuits
… ports to their closest pads using a bipartite weighted matching algorithm. The third stage physically connects together the I/O ports to the closest pads using a modified maze router based on A* search. Finally, the resulted layout of the area-array padframe is added to the chip core to …
-
The Use of Formal Grammars in Automatic Speech Recognition
… of a string involves the use of the ‘weighted matching network' technique in the FSG approach and the computation of the minimisation matrix M for the CFG approach. Both the FSG and CFG models offer comparable recognition performances whilst the use of the CFG approach results in an …
-
The Cirsium altissimum - discolor Complex in Illinois
… set of character states was computed using a weighted matching coefficient (weight=F-1). Two non-overlapping parental curves and an intermediate curve of sterile plants were produced. It was concluded that Cirsium altissimum and C. discolor were undergoing hybridization in Illinois. The areas …
-
Matchings and games on networks
… shows that deciding the existence of a stable matching in our model is NP-complete. We then use our model to study a long standing open problem about cyclic 3D stable matchings. In particular, we prove that deciding whether a fixed 2D perfect matching can be extended to a 3D stable matching is …
-
SCHEDULING AND RATE PROVISIONING FOR INPUT-BUFERED CELL BASED SWITCH FABRICS
… us to the introduction of maximum node contained matching (MNCM) a new class of deterministic maximal size matching algorithms. We use fluid model techniques to prove that these algorithms achieve 100% throughput with no speedup. The only assumption on the arrival pattern is that it satisfies …
-
Net zero energy buildings integrated with multi-generation technologies: Balance metrics, energy matching and economic analyses
… These aspects are the balance metric, energy matching capability, and economic viability. Integrating renewable energy systems with high efficient energy buildings to fulfill the NZEB balance is inevitable. More attention is paid to micro and small scale multi-generation systems including …
-
Input Sensitive Analysis of a Minimum Metric Bipartite Matching Algorithm
… In this thesis, we consider the online bipartite matching problem where each server can serve exactly one request. In the online minimum metric bipartite matching problem, we are provided with a set of server locations in a metric space. Requests arrive one at a time that have to be immediately …
-
Computing the Nucleolus of Matching and b-Matching Games
In the classical weighted matching problem the optimizer is given a graph with edge weights and their goal is to find a matching which maximizes the sum of the weights of edges in the matching. It is typically assumed in this process that the optimizer has unilateral control over the decision to …
-
A modified t-test for treatment means in unreplicated classroom comparisons and Matching Methods for reducing data imbalance
… controlled and randomized treatment assignment, matching methods are often used to increase the similarity in the joint and marginal covariate distributions between a treated and an untreated sample to reduce the difference in the observed response of interest due to differences in covariates. …
-
Scalable cost-efficient placement and chaining of virtual network functions
… on an extension of the well-known reduction from weighted matching to min-cost flow problem. Finally, we tackle the problem of monitoring service chains in NFV-based environments. For that, we introduce the DNM (Distributed Network Monitoring) problem and propose an optimization model to solve it. …