Zobrazeno 1 - 10
of 93
pro vyhledávání: '"Spoerhase, Joachim"'
We initiate the study of the following general clustering problem. We seek to partition a given set $P$ of data points into $k$ clusters by finding a set $X$ of $k$ centers and assigning each data point to one of the centers. The cost of a cluster, r
Externí odkaz:
http://arxiv.org/abs/2410.24104
We give improved approximations for two metric Traveling Salesman Problem (TSP) variants. In Ordered TSP (OTSP) we are given a linear ordering on a subset of nodes $o_1, \ldots, o_k$. The TSP solution must have that $o_{i+1}$ is visited at some point
Externí odkaz:
http://arxiv.org/abs/2405.12876
This paper studies $k$-claw-free graphs, exploring the connection between an extremal combinatorics question and the power of a convex program in approximating the maximum-weight independent set in this graph class. For the extremal question, we cons
Externí odkaz:
http://arxiv.org/abs/2308.16033
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:
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:
Bekos, Michael A., van Dijk, Thomas C., Fink, Martin, Kindermann, Philipp, Kobourov, Stephen, Pupyrev, Sergey, Spoerhase, Joachim, Wolff, Alexander
We study the following geometric representation problem: Given a graph whose vertices correspond to axis-aligned rectangles with fixed dimensions, arrange the rectangles without overlaps in the plane such that two rectangles touch if the graph contai
Externí odkaz:
http://hdl.handle.net/10150/623076
http://arizona.openrepository.com/arizona/handle/10150/623076
http://arizona.openrepository.com/arizona/handle/10150/623076
Autor:
Gutowski, Grzegorz, Mittelstädt, Florian, Rutter, Ignaz, Spoerhase, Joachim, Wolff, Alexander, Zink, Johannes
A mixed graph has a set of vertices, a set of undirected egdes, and a set of directed arcs. A proper coloring of a mixed graph $G$ is a function $c$ that assigns to each vertex in $G$ a positive integer such that, for each edge $uv$ in $G$, $c(u) \ne
Externí odkaz:
http://arxiv.org/abs/2208.14250
Autor:
Firman, Oksana, Spoerhase, Joachim
We propose a new representation of $k$-partite, $k$-uniform hypergraphs, that is, a hypergraph with a partition of vertices into $k$ parts such that each hyperedge contains exactly one vertex of each type; we call them $k$-hypergraphs for short. Give
Externí odkaz:
http://arxiv.org/abs/2111.13555
Autor:
Chalermsook, Parinya, Kaul, Matthias, Mnich, Matthias, Spoerhase, Joachim, Uniyal, Sumedha, Vaz, Daniel
The fundamental sparsest cut problem takes as input a graph $G$ together with the edge costs and demands, and seeks a cut that minimizes the ratio between the costs and demands across the cuts. For $n$-node graphs~$G$ of treewidth~$k$, \chlamtac, Kra
Externí odkaz:
http://arxiv.org/abs/2111.06299
The Polyline Bundle Simplification (PBS) problem is a generalization of the classical polyline simplification problem. Given a set of polylines, which may share line segments and points, PBS asks for the smallest consistent simplification of these po
Externí odkaz:
http://arxiv.org/abs/2108.10790