English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Motivated by several applications, we consider the problem of randomlyrounding a fractional solution in a matroid (base) polytope to an integral one.We consider the pipage rounding technique and also present a new technique,randomized swap rounding. Our main technical results are concentration boundsfor functions of random variables arising from these rounding techniques. Weprove Chernoff-type concentration bounds for linear functions of randomvariables arising from both techniques, and also a lower-tail exponential boundfor monotone submodular functions of variables arising from randomized swaprounding.  The following are examples of our applications: (1) We give a(1-1/e-epsilon)-approximation algorithm for the problem of maximizing amonotone submodular function subject to 1 matroid and k linear constraints, forany constant k and epsilon>0. (2) We present a result on minimax packingproblems that involve a matroid base constraint. We give an O(log m / log logm)-approximation for the general problem Min {lambda: x \in {0,1}^N, x \inB(M), Ax <= lambda b}, where m is the number of packing constraints. (3) Wegeneralize the continuous greedy algorithm to problems involving multiplesubmodular functions, and use it to find a (1-1/e-epsilon)-approximate paretoset for the problem of maximizing a constant number of monotone submodularfunctions subject to a matroid constraint. An example is the Submodular WelfareProblem where we are looking for an approximate pareto set with respect toindividual players' utilities.

Dependent Randomized Rounding for Matroid Polytopes and Applications