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"”.
-
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 …
-
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 …
-
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 …
-
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 …