Concept
Dominating set
Related publications (56)
Safe Zeroth-Order Convex Optimization Using Quadratic Local Approximations
Giancarlo Ferrari Trecate, Maryam Kamgarpour, Yuning Jiang, Baiwei Guo
We address black-box convex optimization problems, where the objective and constraint functions are not explicitly known but can be sampled within the feasible set. The challenge is thus to generate a sequence of feasible points converging towards an optim ...
2023Random walks and forbidden minors III: poly(d epsilon(-1))-time partition oracles for minor-free graph classes
Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, one removes a small ...
IEEE COMPUTER SOC2022The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness
Ola Nils Anders Svensson, Moran Feldman, Rico Zenklusen, Ashkan Norouzi Fard
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 t ...
ASSOC COMPUTING MACHINERY2020Ordered Graphs And Large Bi-Cliques In Intersection Graphs Of Curves
An ordered graph G(
COMENIUS UNIV2019Ordered graphs and large bi-cliques in intersection graphs of curves
An ordered graph G(
ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD2019No Small Linear Program Approximates Vertex Cover Within a Factor 2-epsilon
Ola Nils Anders Svensson, Abbas Bazzi
The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev [Khot S, Regev O (2008) Vertex cover might be hard to approximate to within 2 - epsilon. J. Comput. System Sci. 74(3): 335-349 ...
INFORMS2019