BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Rico Zenklusen

Rico Zenklusen contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and Algorithmsmath.OCDiscrete Mathematics

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
7works
0followers
3topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

7 published item(s)

preprint2022arXiv

Better-Than-$\frac{4}{3}$-Approximations for Leaf-to-Leaf Tree and Connectivity Augmentation

The Connectivity Augmentation Problem (CAP) together with a well-known special case thereof known as the Tree Augmentation Problem (TAP) are among the most basic Network Design problems. There has been a surge of interest recently to find approximation algorithms with guarantees below $2$ for both TAP and CAP, culminating in the currently best approximation factor for both problems of $1.393$ through quite sophisticated techniques. We present a new and arguably simple matching-based method for the well-known special case of leaf-to-leaf instances. Combining our work with prior techniques, we readily obtain a $(\frac{4}{3}+ε)$-approximation for Leaf-to-Leaf CAP by returning the better of our solution and one of an existing method. Prior to our work, a $\frac{4}{3}$-guarantee was only known for Leaf-to-Leaf TAP instances on trees of height $2$. Moreover, when combining our technique with a recently introduced stack analysis approach, which is part of the above-mentioned $1.393$-approximation, we can further improve the approximation factor to $1.29$, obtaining for the first time a factor below $\frac{4}{3}$ for a nontrivial class of TAP/CAP instances.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Extension Complexity Lower Bounds for Mixed-Integer Extended Formulations

We prove that any mixed-integer linear extended formulation for the matching polytope of the complete graph on $n$ vertices, with a polynomial number of constraints, requires $Ω(\sqrt{\sfrac{n}{\log n}})$ many integer variables. By known reductions, this result extends to the traveling salesman polytope. This lower bound has various implications regarding the existence of small mixed-integer mathematical formulations of common problems in operations research. In particular, it shows that for many classic vehicle routing problems and problems involving matchings, any compact mixed-integer linear description of such a problem requires a large number of integer variables. This provides a first non-trivial lower bound on the number of integer variables needed in such settings.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Streaming Submodular Maximization under Matroid Constraints

Recent progress in (semi-)streaming algorithms for monotone submodular function maximization has led to tight results for a simple cardinality constraint. However, current techniques fail to give a similar understanding for natural generalizations, including matroid constraints. This paper aims at closing this gap. For a single matroid of rank $k$ (i.e., any solution has cardinality at most $k$), our main results are: 1) a single-pass streaming algorithm that uses $\widetilde{O}(k)$ memory and achieves an approximation guarantee of $0.3178$, and 2) a multi-pass streaming algorithm that uses $\widetilde{O}(k)$ memory and achieves an approximation guarantee of $(1-1/e - \varepsilon)$ by taking a constant (depending on $\varepsilon$) number of passes over the stream. This improves on the previously best approximation guarantees of $1/4$ and $1/2$ for single-pass and multi-pass streaming algorithms, respectively. In fact, our multi-pass streaming algorithm is tight in that any algorithm with a better guarantee than $1/2$ must make several passes through the stream and any algorithm that beats our guarantee of $1-1/e$ must make linearly many passes (as well as an exponential number of value oracle queries). Moreover, we show how the approach we use for multi-pass streaming can be further strengthened if the elements of the stream arrive in uniformly random order, implying an improved result for $p$-matchoid constraints.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Submodular Maximization Subject to Matroid Intersection on the Fly

Despite a surge of interest in submodular maximization in the data stream model, there remain significant gaps in our knowledge about what can be achieved in this setting, especially when dealing with multiple constraints. In this work, we nearly close several basic gaps in submodular maximization subject to $k$ matroid constraints in the data stream model. We present a new hardness result showing that super polynomial memory in $k$ is needed to obtain an $o(k / \log k)$-approximation. This implies near optimality of prior algorithms. For the same setting, we show that one can nevertheless obtain a constant-factor approximation by maintaining a set of elements whose size is independent of the stream size. Finally, for bipartite matching constraints, a well-known special case of matroid intersection, we present a new technique to obtain hardness bounds that are significantly stronger than those obtained with prior approaches. Prior results left it open whether a $2$-approximation may exist in this setting, and only a complexity-theoretic hardness of $1.91$ was known. We prove an unconditional hardness of $2.69$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Techniques for Generalized Colorful $k$-Center Problems

Fair clustering enjoyed a surge of interest recently. One appealing way of integrating fairness aspects into classical clustering problems is by introducing multiple covering constraints. This is a natural generalization of the robust (or outlier) setting, which has been studied extensively and is amenable to a variety of classic algorithmic techniques. In contrast, for the case of multiple covering constraints (the so-called colorful setting), specialized techniques have only been developed recently for $k$-Center clustering variants, which is also the focus of this paper. While prior techniques assume covering constraints on the clients, they do not address additional constraints on the facilities, which has been extensively studied in non-colorful settings. In this paper, we present a quite versatile framework to deal with various constraints on the facilities in the colorful setting, by combining ideas from the iterative greedy procedure for Colorful $k$-Center by Inamdar and Varadarajan with new ingredients. To exemplify our framework, we show how it leads, for a constant number $γ$ of colors, to the first constant-factor approximations for both Colorful Matroid Supplier with respect to a linear matroid and Colorful Knapsack Supplier. In both cases, we readily get an $O(2^γ)$-approximation. Moreover, for Colorful Knapsack Supplier, we show that it is possible to obtain constant approximation guarantees that are independent of the number of colors $γ$, as long as $γ=O(1)$, which is needed to obtain a polynomial running time. More precisely, we obtain a $7$-approximation by extending a technique recently introduced by Jia, Sheth, and Svensson for Colorful $k$-Center.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Technique for Obtaining True Approximations for $k$-Center with Covering Constraints

There has been a recent surge of interest in incorporating fairness aspects into classical clustering problems. Two recently introduced variants of the $k$-Center problem in this spirit are Colorful $k$-Center, introduced by Bandyapadhyay, Inamdar, Pai, and Varadarajan, and lottery models, such as the Fair Robust $k$-Center problem introduced by Harris, Pensyl, Srinivasan, and Trinh. To address fairness aspects, these models, compared to traditional $k$-Center, include additional covering constraints. Prior approximation results for these models require to relax some of the normally hard constraints, like the number of centers to be opened or the involved covering constraints, and therefore, only obtain constant-factor pseudo-approximations. In this paper, we introduce a new approach to deal with such covering constraints that leads to (true) approximations, including a $4$-approximation for Colorful $k$-Center with constantly many colors---settling an open question raised by Bandyapadhyay, Inamdar, Pai, and Varadarajan---and a $4$-approximation for Fair Robust $k$-Center, for which the existence of a (true) constant-factor approximation was also open. We complement our results by showing that if one allows an unbounded number of colors, then Colorful $k$-Center admits no approximation algorithm with finite approximation guarantee, assuming that $\mathrm{P} \neq \mathrm{NP}$. Moreover, under the Exponential Time Hypothesis, the problem is inapproximable if the number of colors grows faster than logarithmic in the size of the ground set.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The One-way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness

We consider the classical problem of maximizing a monotone submodular function subject to a cardinality constraint, which, due to its numerous applications, has recently been studied in various computational models. We consider a clean multi-player model that lies between the offline and streaming model, and study it under the aspect of one-way communication complexity. Our model captures the streaming setting (by considering a large number of players), and, in addition, two player approximation results for it translate into the robust setting. We present tight one-way communication complexity results for our model, which, due to the above-mentioned connections, have multiple implications in the data stream and robust setting. Even for just two players, a prior information-theoretic hardness result implies that no approximation factor above $1/2$ can be achieved in our model, if only queries to feasible sets are allowed. We show that the possibility of querying infeasible sets can actually be exploited to beat this bound, by presenting a tight $2/3$-approximation taking exponential time, and an efficient $0.514$-approximation. To the best of our knowledge, this is the first example where querying a submodular function on infeasible sets leads to provably better results. Through the above-mentioned link to the robust setting, both of these algorithms improve on the current state-of-the-art for robust submodular maximization, showing that approximation factors beyond $1/2$ are possible. Moreover, exploiting the link of our model to streaming, we settle the approximability for streaming algorithms by presenting a tight $1/2+\varepsilon$ hardness result, based on the construction of a new family of coverage functions. This improves on a prior $1-1/e+\varepsilon$ hardness and matches, up to an arbitrarily small margin, the best known approximation algorithm.

0 citations0 reviewsNo code linkedOpen access