Zobrazeno 1 - 10
of 122
pro vyhledávání: '"Zeev Nutov"'
Publikováno v:
Algorithmica. 85:1332-1371
We consider the problem of maximizing a non-negative monotone submodular function subject to a knapsack constraint, which is also known as the Budgeted Submodular Maximization (BSM) problem. Sviridenko (2004) showed that by guessing 3 appropriate ele
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3ecd46248a15555266a79cfd6d36c89a
https://doi.org/10.1007/s00453-022-01071-2
https://doi.org/10.1007/s00453-022-01071-2
Publikováno v:
Wireless Networks. 29:209-220
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c79e36a2fdd916cacd4841981e70a8c3
https://doi.org/10.1007/s11276-022-03120-8
https://doi.org/10.1007/s11276-022-03120-8
Autor:
Zeev Nutov
Publikováno v:
Journal of Computer and System Sciences. 123:64-75
We obtain approximation ratio 4 + 2 l ≈ 4 + 4 lg k lg n − lg k for the (undirected) k -Connected Subgraph problem, where l = ⌊ lg n − lg k + 1 2 lg k + 1 ⌋ is the largest integer such that 2 l − 1 k 2 l + 1 ≤ n .
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::8f2a83a5c68be4a179dcc530c6b70a5c
https://doi.org/10.1016/j.jcss.2021.07.006
https://doi.org/10.1016/j.jcss.2021.07.006
Publikováno v:
IEEE/ACM Transactions on Networking. :1-16
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::0eae319824c5ad46f9df17989ef913ac
https://doi.org/10.1109/tnet.2022.3231184
https://doi.org/10.1109/tnet.2022.3231184
Autor:
Zeev Nutov
Publikováno v:
Algorithmica. 83:553-575
In the Tree Augmentation problem we are given a tree T=(V,F) and a set E of edges with positive integer costs {c_e:e in E}. The goal is to augment T by a minimum cost edge set J subseteq E such that T cup J is 2-edge-connected. We obtain the followin
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::7cb975d32d90240139a5c65eb67d6fc9
https://doi.org/10.1007/s00453-020-00765-9
https://doi.org/10.1007/s00453-020-00765-9
Autor:
Zeev Nutov
Publikováno v:
Information Processing Letters. 140:30-33
A graph is k-connected if it has k pairwise internally node disjoint paths between every pair of its nodes. A subset S of nodes in a graph G is a k-connected set if the subgraph G [ S ] induced by S is k-connected; S is an m-dominating set if every v
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::cb59caddcf5af6b8e98df981dfa6817c
https://doi.org/10.1016/j.ipl.2018.08.003
https://doi.org/10.1016/j.ipl.2018.08.003
Autor:
Zeev Nutov
Publikováno v:
Computer Science – Theory and Applications ISBN: 9783030794156
CSR
CSR
We consider the directed Rooted Subset k -Edge-Connectivity problem: given a digraph \(G=(V,E)\) with edge costs, a set \(T \subset V\) of terminals, a root node r, and an integer k, find a min-cost subgraph of G that contains k edge disjoint rt-path
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::779614b1512414b2c5db2169426fb930
https://doi.org/10.1007/978-3-030-79416-3_20
https://doi.org/10.1007/978-3-030-79416-3_20
Autor:
Zeev Nutov
Publikováno v:
Approximation and Online Algorithms ISBN: 9783030808785
WAOA
WAOA
We consider network design problems in which we are given a graph \(G=(V,E)\) with edge costs, and seek a min-cost/size 2-node-connected subgraph \(G'=(V',E')\) that satisfies a prescribed property.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::155f4724efab47f834f405d426956639
https://doi.org/10.1007/978-3-030-80879-2_15
https://doi.org/10.1007/978-3-030-80879-2_15
Publikováno v:
Algorithms for Sensor Systems ISBN: 9783030624002
ALGOSENSORS
ALGOSENSORS
In this paper we study covering problems that arise in wireless networks with Unmanned Aerial Vehicles (UAVs) swarms. In the general setting we want to place a set of UAVs that should cover a given set of planar users under some constraints and we wa
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::696fecd636841291c2ab2a5cfad4eb80
https://doi.org/10.1007/978-3-030-62401-9_3
https://doi.org/10.1007/978-3-030-62401-9_3
Autor:
Guy Kortsarz, Zeev Nutov
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783030489656
IWOCA
IWOCA
Motivated by some open problems posed in [13], we study three problems that seek a low degree subtree T of a graph \(G=(V,E)\). In the Min-Degree Group Steiner Tree problem we are given a collection of node subsets (groups), and T should contain a no
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::987e12f23212682c02350a06e7310371
https://doi.org/10.1007/978-3-030-48966-3_26
https://doi.org/10.1007/978-3-030-48966-3_26