TY - CONF
AB - We consider a natural extension to the metric uncapacitated Facility Location Problem (FLP) in which requests ask for different commodities out of a finite set \( S \) of commodities.
Ravi and Sinha (SODA 2004) introduced the model as the \emph{Multi-Commodity Facility Location Problem} (MFLP) and considered it an offline optimization problem.
The model itself is similar to the FLP: i.e., requests are located at points of a finite metric space and the task of an algorithm is to construct facilities and assign requests to facilities while minimizing the construction cost and the sum over all assignment distances.
In addition, requests and facilities are heterogeneous; they request or offer multiple commodities out of $S$.
A request has to be connected to a set of facilities jointly offering the commodities demanded by it.
In comparison to the FLP, an algorithm has to decide not only if and where to place facilities, but also which commodities to offer at each.
To the best of our knowledge we are the first to study the problem in its online variant in which requests, their positions and their commodities are not known beforehand but revealed over time.
We present results regarding the competitive ratio.
On the one hand, we show that heterogeneity influences the competitive ratio by developing a lower bound on the competitive ratio for any randomized online algorithm of \( \Omega ( \sqrt{|S|} + \frac{\log n}{\log \log n} ) \) that already holds for simple line metrics.
Here, \( n \) is the number of requests.
On the other side, we establish a deterministic \( \mathcal{O}(\sqrt{|S|} \cdot \log n) \)-competitive algorithm and a randomized \( \mathcal{O}(\sqrt{|S|} \cdot \frac{\log n}{\log \log n} ) \)-competitive algorithm.
Further, we show that when considering a more special class of cost functions for the construction cost of a facility, the competitive ratio decreases given by our deterministic algorithm depending on the function.
AU - Castenow, Jannik
AU - Feldkord, Björn
AU - Knollmann, Till
AU - Malatyali, Manuel
AU - Meyer auf der Heide, Friedhelm
ID - 17370
KW - Online Multi-Commodity Facility Location
KW - Competitive Ratio
KW - Online Optimization
KW - Facility Location Problem
SN - 9781450369350
T2 - Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures
TI - The Online Multi-Commodity Facility Location Problem
ER -
TY - THES
AU - Feldkord, Björn
ID - 15631
TI - Mobile Resource Allocation
ER -
TY - CONF
AU - Feldkord, Björn
AU - Knollmann, Till
AU - Malatyali, Manuel
AU - Meyer auf der Heide, Friedhelm
ID - 12870
T2 - Proceedings of the 17th Workshop on Approximation and Online Algorithms (WAOA)
TI - Managing Multiple Mobile Resources
ER -
TY - JOUR
AU - Feldkord, Björn
AU - Meyer auf der Heide, Friedhelm
ID - 13873
IS - 3
JF - ACM Transactions on Parallel Computing (TOPC)
TI - The Mobile Server Problem
VL - 6
ER -
TY - CHAP
AU - Feldkord, Björn
AU - Malatyali, Manuel
AU - Meyer auf der Heide, Friedhelm
ID - 16392
SN - 0302-9743
T2 - Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications
TI - A Dynamic Distributed Data Structure for Top-k and k-Select Queries
ER -
TY - CONF
AB - We study the classic bin packing problem in a fully-dynamic setting, where new items can arrive and old items may depart. We want algorithms with low asymptotic competitive ratio while repacking items sparingly between updates. Formally, each item i has a movement cost c_i >= 0, and we want to use alpha * OPT bins and incur a movement cost gamma * c_i, either in the worst case, or in an amortized sense, for alpha, gamma as small as possible. We call gamma the recourse of the algorithm. This is motivated by cloud storage applications, where fully-dynamic bin packing models the problem of data backup to minimize the number of disks used, as well as communication incurred in moving file backups between disks. Since the set of files changes over time, we could recompute a solution periodically from scratch, but this would give a high number of disk rewrites, incurring a high energy cost and possible wear and tear of the disks. In this work, we present optimal tradeoffs between number of bins used and number of items repacked, as well as natural extensions of the latter measure.
AU - Feldkord, Björn
AU - Feldotto, Matthias
AU - Gupta, Anupam
AU - Guruganesh, Guru
AU - Kumar, Amit
AU - Riechers, Sören
AU - Wajc, David
ED - Chatzigiannakis, Ioannis
ED - Kaklamanis, Christos
ED - Marx, Dániel
ED - Sannella, Donald
ID - 2484
SN - 1868-8969
T2 - 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
TI - Fully-Dynamic Bin Packing with Little Repacking
VL - 107
ER -
TY - CONF
AU - Feldkord, Björn
AU - Meyer auf der Heide, Friedhelm
ID - 2485
T2 - Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)
TI - Online Facility Location with Mobile Facilities
ER -
TY - CONF
AB - We introduce the mobile server problem, inspired by current trends to move computational tasks from cloud structures to multiple devices close to the end user. An example for this are embedded systems in autonomous cars that communicate in order to coordinate their actions. Our model is a variant of the classical Page Migration Problem. Moreformally, we consider a mobile server holding a data page.The server can move in the Euclidean space (of arbitrary dimension). In every round, requests for data items from the page pop up at arbitrary points in the space. The requests are served, each at a cost of the distance from the requesting point and the server, and the mobile server may move, at a cost D times the distance traveled for some constant D . We assume a maximum distance m the server is allowed to move per round. We show that no online algorithm can achieve a competitive ratio independent of the length of the input sequence in this setting. Hence we augment the maximum movement distance of the online algorithms to ( 1 + δ) times the maximum distance of the offline solution. We provide a deterministic algorithm which is simple to describe and works for multiple variants of our problem. The algorithm achieves almost tight competitive ratios independent of the length of the input sequence.
AU - Feldkord, Björn
AU - Meyer auf der Heide, Friedhelm
ID - 55
T2 - Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)
TI - The Mobile Server Problem
ER -
TY - CONF
AU - Biermeier, Felix
AU - Feldkord, Björn
AU - Malatyali, Manuel
AU - Meyer auf der Heide, Friedhelm
ID - 16348
T2 - Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA)
TI - A Communication-Efficient Distributed Data Structure for Top-k and k-Select Queries
ER -
TY - CONF
AU - Feldkord, Björn
AU - Markarian, Christine
AU - Meyer auf der Heide, Friedhelm
ID - 70
T2 - Proceedings of the 11th Annual International Conference on Combinatorial Optimization and Applications (COCOA)
TI - Price Fluctuations in Online Leasing
ER -
TY - CONF
AB - In this paper we consider a strategic variant of the online facility location problem. Given is a graph in which each node serves two roles: it is a strategic client stating requests as well as a potential location for a facility. In each time step one client states a request which induces private costs equal to the distance to the closest facility. Before serving, the clients may collectively decide to open new facilities, sharing the corresponding price. Instead of optimizing the global costs, each client acts selfishly. The prices of new facilities vary between nodes and also change over time, but are always bounded by some fixed value α. Both the requests as well as the facility prices are given by an online sequence and are not known in advance.We characterize the optimal strategies of the clients and analyze their overall performance in comparison to a centralized offline solution. If all players optimize their own competitiveness, the global performance of the system is O(√α⋅α) times worse than the offline optimum. A restriction to a natural subclass of strategies improves this result to O(α). We also show that for fixed facility costs, we can find strategies such that this bound further improves to O(√α).
AU - Drees, Maximilian
AU - Feldkord, Björn
AU - Skopalik, Alexander
ID - 149
T2 - Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)
TI - Strategic Online Facility Location
ER -
TY - GEN
AU - Feldkord, Björn
ID - 391
TI - On Variants of the Page Migration Problem
ER -
TY - GEN
AU - Feldkord, Björn
ID - 600
TI - Lokale Swaps und überholte Informationen in Basic Network Creation Games
ER -