Zobrazeno 1 - 10
of 84
pro vyhledávání: '"Byrka, Jarosław"'
The Steiner tree problem is one of the most prominent problems in network design. Given an edge-weighted undirected graph and a subset of the vertices, called terminals, the task is to compute a minimum-weight tree containing all terminals (and possi
Externí odkaz:
http://arxiv.org/abs/2407.19905
In the online disjoint set covers problem, the edges of a hypergraph are revealed online, and the goal is to partition them into a maximum number of disjoint set covers. That is, n nodes of a hypergraph are given at the beginning, and then a sequence
Externí odkaz:
http://arxiv.org/abs/2404.15554
Submodularity in combinatorial optimization has been a topic of many studies and various algorithmic techniques exploiting submodularity of a studied problem have been proposed. It is therefore natural to ask, in cases where the cost function of the
Externí odkaz:
http://arxiv.org/abs/2305.10935
Autor:
Abbasi, Fateme, Banerjee, Sandip, Byrka, Jarosław, Chalermsook, Parinya, Gadekar, Ameet, Khodamoradi, Kamyar, Marx, Dániel, Sharma, Roohani, Spoerhase, Joachim
Publikováno v:
51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), Leibniz International Proceedings in Informatics (LIPIcs), vol. 297, pp. 6:1--6:19, Schloss Dagstuhl -- Leibniz-Zentrum f\"ur Informatik, 2024
We consider the well-studied Robust $(k, z)$-Clustering problem, which generalizes the classic $k$-Median, $k$-Means, and $k$-Center problems. Given a constant $z\ge 1$, the input to Robust $(k, z)$-Clustering is a set $P$ of $n$ weighted points in a
Externí odkaz:
http://arxiv.org/abs/2305.07316
Autor:
Turko, Andrzej, Byrka, Jarosław
We study an envy-free pricing problem, in which each buyer wishes to buy a shortest path connecting her individual pair of vertices in a network owned by a single vendor. The vendor sets the prices of individual edges with the aim of maximizing the t
Externí odkaz:
http://arxiv.org/abs/2305.05405
Autor:
Abbasi, Fateme, Banerjee, Sandip, Byrka, Jarosław, Chalermsook, Parinya, Gadekar, Ameet, Khodamoradi, Kamyar, Marx, Dániel, Sharma, Roohani, Spoerhase, Joachim
This paper considers the well-studied algorithmic regime of designing a $(1+\epsilon)$-approximation algorithm for a $k$-clustering problem that runs in time $f(k,\epsilon)poly(n)$ (sometimes called an efficient parameterized approximation scheme or
Externí odkaz:
http://arxiv.org/abs/2304.03146
Autor:
Abbasi, Fateme, Adamczyk, Marek, Bosch-Calvo, Miguel, Byrka, Jarosław, Grandoni, Fabrizio, Sornat, Krzysztof, Tinguely, Antoine
In the Submodular Facility Location problem (SFL) we are given a collection of $n$ clients and $m$ facilities in a metric space. A feasible solution consists of an assignment of each client to some facility. For each client, one has to pay the distan
Externí odkaz:
http://arxiv.org/abs/2211.05474
We study the problem of online facility location with delay. In this problem, a sequence of $n$ clients appear in the metric space, and they need to be eventually connected to some open facility. The clients do not have to be connected immediately, b
Externí odkaz:
http://arxiv.org/abs/2110.15155
The $k$-Median problem is one of the well-known optimization problems that formalize the task of data clustering. Here, we are given sets of facilities $F$ and clients $C$, and the goal is to open $k$ facilities from the set $F$, which provides the b
Externí odkaz:
http://arxiv.org/abs/2011.08083
Autor:
Byrka, Jarosław, Lewandowski, Mateusz
We study a variant of the uncapacitated facility location problem (UFL), where connection costs of clients are defined by (client specific) concave nondecreasing functions of the connection distance in the underlying metric. A special case capturing
Externí odkaz:
http://arxiv.org/abs/1912.00770