Zobrazeno 1 - 10
of 128
pro vyhledávání: '"Hadas Shachnai"'
Autor:
Hadas Shachnai, Lisa Zhang
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol DMTCS Proceedings vol. AD,..., Iss Proceedings (2005)
We consider the $\textit{master ring problem (MRP)}$ which often arises in optical network design. Given a network which consists of a collection of interconnected rings $R_1, \ldots, R_K$, with $n_1, \ldots, n_K$ distinct nodes, respectively, we nee
Externí odkaz:
https://doaj.org/article/6df54a138d0f42c69786ccefe6a5d2f0
Publikováno v:
Journal of Computer and System Sciences. 125:149-165
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5ae6e7d4b12272b7bcb664a685ccf6b1
https://doi.org/10.1016/j.jcss.2021.11.005
https://doi.org/10.1016/j.jcss.2021.11.005
Publikováno v:
Discrete Applied Mathematics. 296:164-178
We prove a general result demonstrating the power of Lagrangian relaxation in solving constrained maximization problems with arbitrary objective functions. This yields a unified approach for solving a wide class of subset selection problems with line
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5b1a2009986e6e54372414637134b5f7
https://doi.org/10.1016/j.dam.2020.10.001
https://doi.org/10.1016/j.dam.2020.10.001
Publikováno v:
Mathematics of Operations Research. 45:1-14
The [Formula: see text]-supplier problem is a fundamental location problem that involves opening [Formula: see text] facilities to minimize the maximum distance of any client to an open facility. We consider the [Formula: see text]-supplier problem i
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c5f5d6ea7cace1e02325590448597988
https://doi.org/10.1287/moor.2018.0953
https://doi.org/10.1287/moor.2018.0953
Publikováno v:
Algorithmica. 81:3217-3244
Motivated by the cloud computing paradigm, and by key optimization problems in all-optical networks, we study two variants of the classic job interval scheduling problem, where a reusable resource is allocated to competing job intervals in a flexible
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::35eeab6725ef7016da9ac7299f73effe
https://doi.org/10.1007/s00453-019-00582-9
https://doi.org/10.1007/s00453-019-00582-9
Publikováno v:
Operations Research Letters
Many algorithms for maximizing a monotone submodular function subject to a knapsack constraint rely on the natural greedy heuristic. We present a novel refined analysis of this greedy heuristic which enables us to: (1) reduce the enumeration in the t
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e1e5df83bdceec8ce6c528b337a3371c
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783030835071
WADS
WADS
We study the following variant of the classic bin packing problem. Given a set of items of various sizes, partitioned into groups, find a packing of the items in a minimum number of identical (unit-size) bins, such that no two items of the same group
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::454e439925c66b0d8787d21e0083acb4
https://doi.org/10.1007/978-3-030-83508-8_21
https://doi.org/10.1007/978-3-030-83508-8_21
Autor:
Ariel Kulik, Hadas Shachnai
Publikováno v:
FOCS
In this paper we introduce randomized branching as a tool for parameterized approximation and develop the mathematical machinery for its analysis. Our algorithms improve the best known running times of parameterized approximation algorithms for Verte
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ca52726a867214c897a85be02ec32baf
https://doi.org/10.1109/focs46700.2020.00076
https://doi.org/10.1109/focs46700.2020.00076
Publikováno v:
Algorithmica. 81:2270-2316
In the Partial Information Network Query (PINQ) problem, we are given a host graph H, and a pattern $${\mathcal {P}}$$P whose topology is partially known. We seek a connected subgraph of H that resembles$${\mathcal {P}}$$P. PINQ is a generalization o
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::dc3ffd6774914a603cc3871fef11400f
https://doi.org/10.1007/s00453-018-00535-8
https://doi.org/10.1007/s00453-018-00535-8
Publikováno v:
Journal of Computer and System Sciences. 93:30-40
We motivate and describe a new parameterized approximation paradigm which studies the interaction between approximation ratio and running time for any parametrization of a given optimization problem. As a key tool, we introduce the concept of an α-s
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::bbca28594ecb5b5306511b326fe2472b
https://doi.org/10.1016/j.jcss.2017.11.001
https://doi.org/10.1016/j.jcss.2017.11.001