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 2 of 2 for “"matching augmentation problem"”.

  1. The Matching Augmentation Problem: A 7/4-Approximation Algorithm

    We present a 7/4 approximation algorithm for the matching augmentation problem (MAP): given a multi-graph with edges of cost either zero or one such that the edges of cost zero form a matching, find a 2-edge connected spanning subgraph (2-ECSS) of minimum cost. We first present a series of …

    waterloo Repository record for The Matching Augmentation Problem: A 7/4-Approximation Algorithm (opens in a new tab)

  2. Exact, Approximate, and Online Algorithms for Optimization Problems Arising in DVD Assignment

    … rental company that faces two major operational problems: calculation of the assignment of DVDs to customers every thirty minutes throughout the day and purchasing of new inventory in regular intervals. In this thesis, we model these two problems and develop algorithms to solve them. In doing so, …

    waterloo Repository record for Exact, Approximate, and Online Algorithms for Optimization Problems Arising in DVD Assignment (opens in a new tab)