@book{16870,
editor = {Flocchini, Paola and Gao, Jie and Kranakis, Evangelos and Meyer auf der Heide, Friedhelm},
isbn = {9783642453458},
issn = {0302-9743},
publisher = {Springer},
title = {{Algorithms for Sensor Systems - 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, {ALGOSENSORS} 2013}},
doi = {10.1007/978-3-642-45346-5},
volume = {8243},
year = {2014},
}
@inproceedings{379,
abstract = {In the leasing variant of Set Cover presented by Anthony et al.[1], elements U arrive over time and must be covered by sets from a familyF of subsets of U. Each set can be leased for K different periods of time.Let |U| = n and |F| = m. Leasing a set S for a period k incurs a cost ckS and allows S to cover its elements for the next lk time steps. The objectiveis to minimize the total cost of the sets leased, such that elements arrivingat any time t are covered by sets which contain them and are leased duringtime t. Anthony et al. [1] gave an optimal O(log n)-approximation forthe problem in the offline setting, unless P = NP [22]. In this paper, wegive randomized algorithms for variants of Set Cover Leasing in the onlinesetting, including a generalization of Online Set Cover with Repetitionspresented by Alon et al. [2], where elements appear multiple times andmust be covered by a different set at each arrival. Our results improve theO(log2(mn)) competitive factor of Online Set Cover with Repetitions [2]to O(log d log(dn)) = O(logmlog(mn)), where d is the maximum numberof sets an element belongs to.},
author = {Abshoff, Sebastian and Markarian, Christine and Meyer auf der Heide, Friedhelm},
booktitle = {Proceedings of the 8th Annual International Conference on Combinatorial Optimization and Applications (COCOA)},
pages = {25--34},
title = {{Randomized Online Algorithms for Set Cover Leasing Problems}},
doi = {10.1007/978-3-319-12691-3_3},
year = {2014},
}
@inproceedings{451,
abstract = {We introduce the concept of budget games. Players choose a set of tasks and each task has a certain demand on every resource in the game. Each resource has a budget. If the budget is not enough to satisfy the sum of all demands, it has to be shared between the tasks. We study strategic budget games, where the budget is shared proportionally. We also consider a variant in which the order of the strategic decisions influences the distribution of the budgets. The complexity of the optimal solution as well as existence, complexity and quality of equilibria are analysed. Finally, we show that the time an ordered budget game needs to convergence towards an equilibrium may be exponential.},
author = {Drees, Maximilian and Riechers, Sören and Skopalik, Alexander},
booktitle = {Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT)},
editor = {Lavi, Ron},
pages = {110--121},
title = {{Budget-restricted utility games with ordered strategic decisions}},
doi = {10.1007/978-3-662-44803-8_10},
year = {2014},
}
@inproceedings{456,
abstract = {We study the existence of approximate pure Nash equilibriain social context congestion games. For any given set of allowed costfunctions F, we provide a threshold value μ(F), and show that for theclass of social context congestion games with cost functions from F, α-Nash dynamics are guaranteed to converge to α-approximate pure Nashequilibrium if and only if α > μ(F).Interestingly, μ(F) is related and always upper bounded by Roughgarden’sanarchy value [19].},
author = {Gairing, Martin and Kotsialou, Grammateia and Skopalik, Alexander},
booktitle = {Proceedings of the 10th International Conference on Web and Internet Economics (WINE)},
pages = {480 -- 485},
title = {{Approximate pure Nash equilibria in Social Context Congestion Games}},
doi = {10.1007/978-3-319-13129-0_43},
year = {2014},
}
@inbook{16395,
author = {Abshoff, Sebastian and Meyer auf der Heide, Friedhelm},
booktitle = {Structural Information and Communication Complexity},
isbn = {9783319096193},
issn = {0302-9743},
title = {{Continuous Aggregation in Dynamic Ad-Hoc Networks}},
doi = {10.1007/978-3-319-09620-9_16},
year = {2014},
}
@unpublished{16460,
abstract = {Consider n nodes connected to a single coordinator. Each node receives an
individual online data stream of numbers and, at any point in time, the
coordinator has to know the k nodes currently observing the largest values, for
a given k between 1 and n. We design and analyze an algorithm that solves this
problem while bounding the amount of messages exchanged between the nodes and
the coordinator. Our algorithm employs the idea of using filters which,
intuitively speaking, leads to few messages to be sent, if the new input is
"similar" to the previous ones. The algorithm uses a number of messages that is
on expectation by a factor of O((log {\Delta} + k) log n) larger than that of
an offline algorithm that sets filters in an optimal way, where {\Delta} is
upper bounded by the largest value observed by any node.},
author = {Mäcker, Alexander and Malatyali, Manuel and Meyer auf der Heide, Friedhelm},
booktitle = {arXiv:1410.7912},
title = {{Online Top-k-Position Monitoring of Distributed Data Streams}},
year = {2014},
}
@inproceedings{368,
abstract = {We consider the problem of scheduling a number of jobs on $m$ identical processors sharing a continuously divisible resource. Each job j comes with a resource requirement r_j \in {0,1}. The job can be processed at full speed if granted its full resource requirement. If receiving only an x-portion of r_j, it is processed at an x-fraction of the full speed. Our goal is to find a resource assignment that minimizes the makespan (i.e., the latest completion time). Variants of such problems, relating the resource assignment of jobs to their \emph{processing speeds}, have been studied under the term discrete-continuous scheduling. Known results are either very pessimistic or heuristic in nature.In this paper, we suggest and analyze a slightly simplified model. It focuses on the assignment of shared continuous resources to the processors. The job assignment to processors and the ordering of the jobs have already been fixed. It is shown that, even for unit size jobs, finding an optimal solution is NP-hard if the number of processors is part of the input. Positive results for unit size jobs include an efficient optimal algorithm for 2 processors. Moreover, we prove that balanced schedules yield a 2-1/m-approximation for a fixed number of processors. Such schedules are computed by our GreedyBalance algorithm, for which the bound is tight.},
author = {Brinkmann, Andre and Kling, Peter and Meyer auf der Heide, Friedhelm and Nagel, Lars and Riechers, Sören and Süss, Tim },
booktitle = {Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
pages = {128--137},
title = {{Scheduling Shared Continuous Resources on Many-Cores}},
doi = {10.1145/2612669.2612698},
year = {2014},
}
@inproceedings{370,
abstract = {Max-min fairness (MMF) is a widely known approach to a fair allocation of bandwidth to each of the users in a network. This allocation can be computed by uniformly raising the bandwidths of all users without violating capacity constraints. We consider an extension of these allocations by raising the bandwidth with arbitrary and not necessarily uniform time-depending velocities (allocation rates). These allocations are used in a game-theoretic context for routing choices, which we formalize in progressive filling games (PFGs).We present a variety of results for equilibria in PFGs. We show that these games possess pure Nash and strong equilibria. While computation in general is NP-hard, there are polynomial-time algorithms for prominent classes of Max-Min-Fair Games (MMFG), including the case when all users have the same source-destination pair. We characterize prices of anarchy and stability for pure Nash and strong equilibria in PFGs and MMFGs when players have different or the same source-destination pairs. In addition, we show that when a designer can adjust allocation rates, it is possible to design games with optimal strong equilibria. Some initial results on polynomial-time algorithms in this direction are also derived. },
author = {Harks, Tobias and Höfer, Martin and Schewior, Kevin and Skopalik, Alexander},
booktitle = {Proceedings of the 33rd Annual IEEE International Conference on Computer Communications (INFOCOM'14)},
pages = {352--360},
title = {{Routing Games with Progressive Filling}},
doi = {10.1109/TNET.2015.2468571},
year = {2014},
}
@inproceedings{452,
abstract = {Today's networks, like the Internet, do not consist of one but a mixture of several interconnected networks. Each has individual qualities and hence the performance of a network node results from the networks' interplay.We introduce a new game theoretic model capturing the interplay between a high-speed backbone network and a low-speed general purpose network. In our model, n nodes are connected by a static network and each node can decide individually to become a gateway node. A gateway node pays a fixed price for its connection to the high-speed network, but can utilize the high-speed network to gain communication distance 0 to all other gateways. Communication distances in the low-speed network are given by the hop distances. The effective communication distance between any two nodes then is given by the shortest path, which is possibly improved by using gateways as shortcuts.Every node v has the objective to minimize its communication costs, given by the sum (SUM-game) or maximum (MAX-game) of the effective communication distances from v to all other nodes plus a fixed price \alpha > 0, if it decides to be a gateway. For both games and different ranges of \alpha, we study the existence of equilibria, the price of anarchy, and convergence properties of best-response dynamics.},
author = {Abshoff, Sebastian and Cord-Landwehr, Andreas and Jung, Daniel and Skopalik, Alexander},
booktitle = {Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT)},
editor = {Lavi, Ron},
pages = {294},
title = {{Brief Announcement: A Model for Multilevel Network Games}},
year = {2014},
}
@inproceedings{477,
abstract = {We consider the k-token dissemination problem, where k initially arbitrarily distributed tokens have to be disseminated to all nodes in a dynamic network (as introduced by Kuhn et al., STOC 2010). In contrast to general dynamic networks, our dynamic networks are unit disk graphs, i.e., nodes are embedded into the Euclidean plane and two nodes are connected if and only if their distance is at most R. Our worst-case adversary is allowed to move the nodes on the plane, but the maximum velocity v_max of each node is limited and the graph must be connected in each round. For this model, we provide almost tight lower and upper bounds for k-token dissemination if nodes are restricted to send only one token per round. It turns out that the maximum velocity v_max is a meaningful parameter to characterize dynamics in our model.},
author = {Abshoff, Sebastian and Benter, Markus and Cord-Landwehr, Andreas and Malatyali, Manuel and Meyer auf der Heide, Friedhelm},
booktitle = {Algorithms for Sensor Systems - 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, {ALGOSENSORS} 2013, Sophia Antipolis, France, September 5-6, 2013, Revised Selected Papers},
pages = {22--34},
title = {{Token Dissemination in Geometric Dynamic Networks}},
doi = {10.1007/978-3-642-45346-5_3},
year = {2013},
}