@inproceedings{157, abstract = {{Consider a scheduling problem in which a set of jobs with interjob communication, canonically represented by a weighted tree, needs to be scheduled on m parallel processors interconnected by a shared communication channel. In each time step, we may allow any processed job to use a certain capacity of the channel in order to satisfy (parts of) its communication demands to adjacent jobs processed in parallel. The goal is to find a schedule that minimizes the makespan and in which communication demands of all jobs are satisfied.We show that this problem is NP-hard in the strong sense even if the number of processors and the maximum degree of the underlying tree is constant.Consequently, we design and analyze simple approximation algorithms with asymptotic approximation ratio 2-2/m in case of paths and a ratio of 5/2 in case of arbitrary trees.}}, author = {{König, Jürgen and Mäcker, Alexander and Meyer auf der Heide, Friedhelm and Riechers, Sören}}, booktitle = {{Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)}}, pages = {{563----577}}, title = {{{Scheduling with Interjob Communication on Parallel Processors}}}, doi = {{10.1007/978-3-319-48749-6_41}}, year = {{2016}}, } @inproceedings{149, abstract = {{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(√α).}}, author = {{Drees, Maximilian and Feldkord, Björn and Skopalik, Alexander}}, booktitle = {{Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)}}, pages = {{593----607}}, title = {{{Strategic Online Facility Location}}}, doi = {{10.1007/978-3-319-48749-6_43}}, year = {{2016}}, } @article{139, abstract = {{We consider online optimization problems in which certain goods have to be acquired in order to provide a service or infrastructure. Classically, decisions for such problems are considered as final: one buys the goods. However, in many real world applications, there is a shift away from the idea of buying goods. Instead, leasing is often a more flexible and lucrative business model. Research has realized this shift and recently initiated the theoretical study of leasing models (Anthony and Gupta in Proceedings of the integer programming and combinatorial optimization: 12th International IPCO Conference, Ithaca, NY, USA, June 25–27, 2007; Meyerson in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23–25 Oct 2005, Pittsburgh, PA, USA, 2005; Nagarajan and Williamson in Discret Optim 10(4):361–370, 2013) We extend this line of work and suggest a more systematic study of leasing aspects for a class of online optimization problems. We provide two major technical results. We introduce the leasing variant of online set multicover and give an O(log(mK)logn)-competitive algorithm (with n, m, and K being the number of elements, sets, and leases, respectively). Our results also imply improvements for the non-leasing variant of online set cover. Moreover, we extend results for the leasing variant of online facility location. Nagarajan and Williamson (Discret Optim 10(4):361–370, 2013) gave an O(Klogn)-competitive algorithm for this problem (with n and K being the number of clients and leases, respectively). We remove the dependency on n (and, thereby, on time). In general, this leads to a bound of O(lmaxloglmax) (with the maximal lease length lmax). For many natural problem instances, the bound improves to O(K2).}}, author = {{Abshoff, Sebastian and Kling, Peter and Markarian, Christine and Meyer auf der Heide, Friedhelm and Pietrzyk, Peter }}, journal = {{Journal of Combinatorial Optimization}}, number = {{4}}, pages = {{ 1197----1216}}, publisher = {{Springer}}, title = {{{Towards the price of leasing online}}}, doi = {{10.1007/s10878-015-9915-5}}, year = {{2016}}, } @article{144, abstract = {{Following the direction pioneered by Fiat and Papadimitriou in their 2010 paper [12], we study the complexity of deciding the existence of mixed equilibria for minimization games where players use valuations other than expectation to evaluate their costs. We consider risk-averse players seeking to minimize the sum V=E+R of expectationE and a risk valuationR of their costs; R is non-negative and vanishes exactly when the cost incurred to a player is constant over all choices of strategies by the other players. In a V-equilibrium, no player could unilaterally reduce her cost.Say that V has the Weak-Equilibrium-for-Expectation property if all strategies supported in a player's best-response mixed strategy incur the same conditional expectation of her cost. We introduce E-strict concavity and observe that every E-strictly concave valuation has the Weak-Equilibrium-for-Expectation property. We focus on a broad class of valuations shown to have the Weak-Equilibrium-for-Expectation property, which we exploit to prove two main complexity results, the first of their kind, for the two simplest cases of the problem:• Two strategies: Deciding the existence of a V-equilibrium is strongly NP-hard for the restricted class of player-specific scheduling games on two ordered links [22], when choosing R as (1)Var (variance), or (2)SD (standard deviation), or (3) a concave linear sum of even moments of small order.• Two players: Deciding the existence of a V-equilibrium is strongly NP-hard when choosing R as (1)γ⋅Var, or (2)γ⋅SD, where γ>0 is the risk-coefficient, or choosing V as (3) a convex combination of E+γ⋅Var and the concave ν-valuationν−1(E(ν(⋅))), where ν(x)=xr, with r≥2. This is a concrete consequence of a general strong NP-hardness result that only needs the Weak-Equilibrium-for-Expectation property and a few additional properties for V; its proof involves a reduction with a single parameter, which can be chosen efficiently so that each valuation satisfies the additional properties.}}, author = {{Monien, Burkhard and Mavronicolas, Marios}}, journal = {{Theoretical Computer Science}}, pages = {{67--96}}, publisher = {{Elsevier}}, title = {{{The complexity of equilibria for risk-modeling valuations}}}, doi = {{10.1016/j.tcs.2016.04.013}}, volume = {{634}}, year = {{2016}}, } @inproceedings{29962, author = {{Stille, Karl Stephan Christian and Böcker, Joachim and Fröhleke, Norbert and Bettentrup, Ralf and Kaiser, Ingo}}, booktitle = {{2016 4th International Istanbul Smart Grid Congress and Fair (ICSG)}}, publisher = {{IEEE}}, title = {{{Integration of home photovoltaic generation into electricity tariff for load optimization}}}, doi = {{10.1109/sgcf.2016.7492441}}, year = {{2016}}, } @inproceedings{29960, author = {{Stille, Karl Stephan Christian and Böcker, Joachim and Fröhleke, Norbert and Bettentrup, Ralf and Kaiser, Ingo}}, booktitle = {{2016 10th International Conference on Compatibility, Power Electronics and Power Engineering (CPE-POWERENG)}}, publisher = {{IEEE}}, title = {{{Supervisional load optimization for households with intelligent domestic appliances}}}, doi = {{10.1109/cpe.2016.7544176}}, year = {{2016}}, } @inproceedings{30607, author = {{Henkenius, Carsten and Fröhleke, Norbert and Böcker, Joachim and Figge, Heiko}}, booktitle = {{2016 IEEE Applied Power Electronics Conference and Exposition (APEC)}}, publisher = {{IEEE}}, title = {{{Numerical optimization of passive line filter components for suppression of electromagnetic interference (EMI)}}}, doi = {{10.1109/apec.2016.7468073}}, year = {{2016}}, } @inproceedings{30605, author = {{Bolte, Sven and Fröhleke, Norbert and Böcker, Joachim}}, booktitle = {{2015 IEEE 3rd Workshop on Wide Bandgap Power Devices and Applications (WiPDA)}}, publisher = {{IEEE}}, title = {{{Efficiency optimization for a power factor correction (PFC) rectifier with gallium nitride transistor}}}, doi = {{10.1109/wipda.2015.7369288}}, year = {{2016}}, } @inproceedings{28483, author = {{Marín López, Andrés and Almenárez-Mendoza, Florina and Arias Cabarcos, Patricia and Díaz Sánchez, Daniel}}, booktitle = {{2016 Mediterranean Ad Hoc Networking Workshop, Med-Hoc-Net 2016, Vilanova i la Geltru, Spain, June 20-22, 2016}}, pages = {{1--8}}, publisher = {{{IEEE}}}, title = {{{Wi-Fi Direct: Lessons learned}}}, doi = {{10.1109/MedHocNet.2016.7528493}}, year = {{2016}}, } @techreport{35989, author = {{Schlegel-Matthies, Kirsten and Gigerenzer, Gerd and Wagner, Gert G.}}, issn = {{2365-919X}}, pages = {{51}}, title = {{{Digitale Welt und Gesundheit. eHealth und mHealth – Chancen und Risiken der Digitalisierung im Gesundheitsbereich}}}, year = {{2016}}, } @article{4239, abstract = {{Confocal Raman spectroscopy is applied to identify ferroelectric domain structure sensitive phonon modes in potassium titanyl phosphate. Therefore, polarization-dependent measurements in various scattering configurations have been performed to characterize the fundamental Raman spectra of the material. The obtained spectra are discussed qualitatively based on an internal mode assignment. In the main part of this work, we have characterized z-cut periodically poled potassium titanyl phosphate in terms of polarity- and structure-sensitive phonon modes. Here, we find vibrations whose intensities are linked to the ferroelectric domain walls. We interpret this in terms of changes in the polarizability originating from strain induced by domain boundaries and the inner field distribution. Hence, a direct and 3D visualization of ferroelectric domain structures becomes possible in potassium titanyl phosphate.}}, author = {{Rüsing, Michael and Eigner, Christof and Mackwitz, P. and Berth, Gerhard and Silberhorn, Christine and Zrenner, Artur}}, issn = {{0021-8979}}, journal = {{Journal of Applied Physics}}, number = {{4}}, publisher = {{AIP Publishing}}, title = {{{Identification of ferroelectric domain structure sensitive phonon modes in potassium titanyl phosphate: A fundamental study}}}, doi = {{10.1063/1.4940964}}, volume = {{119}}, year = {{2016}}, } @inproceedings{46364, abstract = {{Automated algorithm configuration procedures play an increasingly important role in the development and application of algorithms for a wide range of computationally challenging problems. Until very recently, these configuration procedures were limited to optimising a single performance objective, such as the running time or solution quality achieved by the algorithm being configured. However, in many applications there is more than one performance objective of interest. This gives rise to the multi-objective automatic algorithm configuration problem, which involves finding a Pareto set of configurations of a given target algorithm that characterises trade-offs between multiple performance objectives. In this work, we introduce MO-ParamILS, a multi-objective extension of the state-of-the-art single-objective algorithm configuration framework ParamILS, and demonstrate that it produces good results on several challenging bi-objective algorithm configuration scenarios compared to a base-line obtained from using a state-of-the-art single-objective algorithm configurator.}}, author = {{Blot, A and Hoos, H and Jourdan, L and Marmion, M and Trautmann, Heike}}, booktitle = {{LION 2016: Learning and Intelligent Optimization}}, editor = {{et al. Joaquin, Vanschooren}}, pages = {{32–47}}, publisher = {{Springer International Publishing}}, title = {{{MO-ParamILS: A Multi-objective Automatic Algorithm Configuration Framework}}}, doi = {{10.1007/978-3-319-50349-3_3}}, volume = {{10079}}, year = {{2016}}, } @inbook{46363, abstract = {{The averaged Hausdorff distance has been proposed as an indicator for assessing the quality of finitely sized approximations of the Pareto front of a multiobjective problem. Since many set-based, iterative optimization algorithms store their currently best approximation in an internal archive these approximations are also termed archives. In case of two objectives and continuous variables it is known that the best approximations in terms of averaged Hausdorff distance are subsets of the Pareto front if it is concave. If it is linear or circularly concave the points of the best approximation are equally spaced. Here, it is proven that the optimal averaged Hausdorff approximation and the Pareto front have an empty intersection if the Pareto front is circularly convex. But the points of the best approximation are equally spaced and they rapidly approach the Pareto front for increasing size of the approximation.}}, author = {{Rudolph, G and Schütze, O and Trautmann, Heike}}, booktitle = {{Applications of Evolutionary Computation: 19$^th$ European Conference, EvoApplications 2016, Porto, Portugal, March 30 — April 1, 2016, Proceedings, Part II}}, editor = {{Squillero, G and Burelli, P}}, isbn = {{978-3-319-31153-1}}, pages = {{42–55}}, publisher = {{Springer International Publishing}}, title = {{{On the Closest Averaged Hausdorff Archive for a Circularly Convex Pareto Front}}}, doi = {{10.1007/978-3-319-31153-1_4}}, year = {{2016}}, } @inproceedings{46369, abstract = {{This paper formally defines multimodality in multiobjective optimization (MO). We introduce a test-bed in which multimodal MO problems with known properties can be constructed as well as numerical characteristics of the resulting landscape. Gradient- and local search based strategies are compared on exemplary problems together with specific performance indicators in the multimodal MO setting. By this means the foundation for Exploratory Landscape Analysis in MO is provided.}}, author = {{Kerschke, Pascal and Wang, Hao and Preuss, Mike and Grimme, Christian and Deutz, André and Trautmann, Heike and Emmerich, Michael}}, booktitle = {{Proceedings of the 14$^th$ International Conference on Parallel Problem Solving from Nature (PPSN XIV)}}, pages = {{962–972}}, publisher = {{Springer}}, title = {{{Towards Analyzing Multimodality of Multiobjective Landscapes}}}, doi = {{10.1007/978-3-319-45823-6_90}}, year = {{2016}}, } @inproceedings{46367, abstract = {{When selecting the best suited algorithm for an unknown optimization problem, it is useful to possess some a priori knowledge of the problem at hand. In the context of single-objective, continuous optimization problems such knowledge can be retrieved by means of Exploratory Landscape Analysis (ELA), which automatically identifies properties of a landscape, e.g., the so-called funnel structures, based on an initial sample. In this paper, we extract the relevant features (for detecting funnels) out of a large set of landscape features when only given a small initial sample consisting of 50 x D observations, where D is the number of decision space dimensions. This is already in the range of the start population sizes of many evolutionary algorithms. The new Multiple Peaks Model Generator (MPM2) is used for training the classifier, and the approach is then very successfully validated on the Black-Box Optimization Benchmark (BBOB) and a subset of the CEC 2013 niching competition problems.}}, author = {{Kerschke, Pascal and Preuss, Mike and Wessing, Simon and Trautmann, Heike}}, booktitle = {{Proceedings of the 18$^th$ Annual Conference on Genetic and Evolutionary Computation}}, isbn = {{978-1-4503-4206-3}}, pages = {{229–236}}, title = {{{Low-Budget Exploratory Landscape Analysis on Multiple Peaks Models}}}, doi = {{10.1145/2908812.2908845}}, year = {{2016}}, } @article{46371, abstract = {{One main task in evolutionary multiobjective optimization (EMO) is to obtain a suitable finite size approximation of the Pareto front which is the image of the solution set, termed the Pareto set, of a given multiobjective optimization problem. In the technical literature, the characteristic of the desired approximation is commonly expressed by closeness to the Pareto front and a sufficient spread of the solutions obtained. In this paper, we first make an effort to show by theoretical and empirical findings that the recently proposed Averaged Hausdorff (or Δ𝑝-) indicator indeed aims at fulfilling both performance criteria for bi-objective optimization problems. In the second part of this paper, standard EMO algorithms combined with a specialized archiver and a postprocessing step based on the Δ𝑝 indicator are introduced which sufficiently approximate the Δ𝑝-optimal archives and generate solutions evenly spread along the Pareto front.}}, author = {{Rudolph, G and Schütze, O and Grimme, C and Domínguez-Medina, C and Trautmann, Heike}}, journal = {{Computational Optimization and Applications (Comput. Optim. Appl.)}}, number = {{2}}, pages = {{589–618}}, title = {{{Optimal averaged Hausdorff archives for bi-objective problems: theoretical and numerical results}}}, doi = {{10.1007/s10589-015-9815-8}}, volume = {{64}}, year = {{2016}}, } @article{46372, abstract = {{We present a new hybrid evolutionary algorithm for the effective hypervolume approximation of the Pareto front of a given differentiable multi-objective optimization problem. Starting point for the local search (LS) mechanism is a new division of the decision space as we will argue that in each of these regions a different LS strategy seems to be most promising. For the LS in two out of the three regions we will utilize and adapt the Directed Search method which is capable of steering the search into any direction given in objective space and which is thus well suited for the problem at hand. We further on integrate the resulting LS mechanism into SMS-EMOA, a state-of-the-art evolutionary algorithm for hypervolume approximations. Finally, we will present some numerical results on several benchmark problems with two and three objectives indicating the strength and competitiveness of the novel hybrid.}}, author = {{Schütze, O and Sosa, Hernandez VA and Trautmann, Heike and Rudolph, G}}, journal = {{Journal of Heuristics}}, number = {{3}}, pages = {{273–300}}, title = {{{The Hypervolume based Directed Search Method for Multi-Objective Optimization Problems}}}, doi = {{10.1007/s10732-016-9310-0}}, volume = {{22}}, year = {{2016}}, } @inproceedings{46368, abstract = {{Exploratory Landscape Analysis (ELA) aims at understanding characteristics of single-objective continuous (black-box) optimization problems in an automated way. Moreover, the approach provides the basis for constructing algorithm selection models for unseen problem instances. Recently, it has gained increasing attention and numerical features have been designed by various research groups. This paper introduces the R-Package FLACCO which makes all relevant features available in a unified framework together with efficient helper functions. Moreover, a case study which gives perspectives to ELA for multi-objective optimization problems is presented.}}, author = {{Kerschke, Pascal and Trautmann, Heike}}, booktitle = {{Proceedings of the IEEE Congress on Evolutionary Computation (CEC)}}, title = {{{The R-Package FLACCO for Exploratory Landscape Analysis with Applications to Multi-Objective Optimization Problems}}}, doi = {{10.1109/CEC.2016.7748359}}, year = {{2016}}, } @inproceedings{11890, abstract = {{In this paper we study the influence of directional radio patterns of Bluetooth low energy (BLE) beacons on smartphone localization accuracy and beacon network planning. A two-dimensional model of the power emission characteristic is derived from measurements of the radiation pattern of BLE beacons carried out in an RF chamber. The Cramer-Rao lower bound (CRLB) for position estimation is then derived for this directional power emission model. With this lower bound on the RMS positioning error the coverage of different beacon network configurations can be evaluated. For near-optimal network planing an evolutionary optimization algorithm for finding the best beacon placement is presented.}}, author = {{Schmalenstroeer, Joerg and Haeb-Umbach, Reinhold}}, booktitle = {{24th European Signal Processing Conference (EUSIPCO 2016)}}, title = {{{Investigations into Bluetooth Low Energy Localization Precision Limits}}}, year = {{2016}}, } @inproceedings{48873, abstract = {{Despite the intrinsic hardness of the Traveling Salesperson Problem (TSP) heuristic solvers, e.g., LKH+restart and EAX+restart, are remarkably successful in generating satisfactory or even optimal solutions. However, the reasons for their success are not yet fully understood. Recent approaches take an analytical viewpoint and try to identify instance features, which make an instance hard or easy to solve. We contribute to this area by generating instance sets for couples of TSP algorithms A and B by maximizing/minimizing their performance difference in order to generate instances which are easier to solve for one solver and much harder to solve for the other. This instance set offers the potential to identify key features which allow to distinguish between the problem hardness classes of both algorithms.}}, author = {{Bossek, Jakob and Trautmann, Heike}}, booktitle = {{Learning and Intelligent Optimization}}, editor = {{Festa, Paola and Sellmann, Meinolf and Vanschoren, Joaquin}}, isbn = {{978-3-319-50349-3}}, keywords = {{Algorithm selection, Feature selection, Instance hardness, TSP}}, pages = {{48–59}}, publisher = {{Springer International Publishing}}, title = {{{Evolving Instances for Maximizing Performance Differences of State-of-the-Art Inexact TSP Solvers}}}, doi = {{10.1007/978-3-319-50349-3_4}}, year = {{2016}}, }