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 6 of 6 for “"submodular function minimization"”.

  1. Combinatorial Algorithms for Submodular Function Minimization and Related Problems

    Submodular functions are common in combinatorics; examples include the cut capacity function of a graph and the rank function of a matroid. The submodular function minimization problem generalizes the classical minimum cut problem and also contains a number of other combinatorial optimization …

    waterloo Repository record for Combinatorial Algorithms for Submodular Function Minimization and Related Problems (opens in a new tab)

  2. Convex Optimization Over Integer Points

    … as the question of minimizing a convex function $f$, which captures the combinatorial structures of the problem, over integer points that are typically $\{0,1\}^n$, i.e. $\min_{x \in \{0,1\}^n} f(x)$. At a high level, this thesis focuses on the efficient solvability and approximability …

    washington Repository record for Convex Optimization Over Integer Points (opens in a new tab)

  3. Submodularity in Natural Language Processing: Algorithms and Applications

    … problems challenge to solve. On the other hand, submodularity, also known as the discrete analogous of convexity, makes many combinatorial optimization problems either tractable or approximable where otherwise neither would be possible. Whether submodularity is applicable to natural language …

    washington Repository record for Submodularity in Natural Language Processing: Algorithms and Applications (opens in a new tab)

  4. Sublinear Algorithm And Lower Bound For Combinatorial Problems

    … Finally, we study the round complexity of submodular function minimization (SFM). In particular, we give a polynomial lower bound on the number of rounds we need to compute s − t max flow - a special case of SFM - in the streaming model. We also prove a polynomial lower bound on the number …

    penn Repository record for Sublinear Algorithm And Lower Bound For Combinatorial Problems (opens in a new tab)