TY - CONF AU - Markarian, Christine AU - Meyer auf der Heide, Friedhelm ID - 13942 T2 - Proceedings of the 8th International Conference on Operations Research and Enterprise Systems TI - Online Algorithms for Leasing Vertex Cover and Leasing Non-metric Facility Location ER - TY - JOUR AU - Abu-Khzam, Faisal N. AU - Li, Shouwei AU - Markarian, Christine AU - Meyer auf der Heide, Friedhelm AU - Podlipyan, Pavel ID - 13946 JF - Theoretical Computer Science TI - Efficient parallel algorithms for parameterized problems VL - 786 ER - TY - JOUR AU - Li, Shouwei AU - Markarian, Christine AU - Meyer auf der Heide, Friedhelm ID - 2848 IS - 5 JF - Algorithmica TI - Towards Flexible Demands in Online Leasing Problems. VL - 80 ER - TY - JOUR AU - Abu-Khzam, Faisal N. AU - Markarian, Christine AU - Meyer auf der Heide, Friedhelm AU - Schubert, Michael ID - 2849 JF - Theory of Computing Systems TI - Approximation and Heuristic Algorithms for Computing Backbones in Asymmetric Ad-hoc Networks ER - TY - CONF AU - Hamann, Heiko AU - Markarian, Christine AU - Meyer auf der Heide, Friedhelm AU - Wahby, Mostafa ID - 2850 T2 - Ninth International Conference on Fun with Algorithms (FUN) TI - Pick, Pack, & Survive: Charging Robots in a Modern Warehouse based on Online Connected Dominating Sets ER - TY - CONF AU - Markarian, Christine ID - 2851 T2 - International Conference on Operations Research (OR) TI - Leasing with Uncertainty ER - TY - CONF AB - Many graph problems such as maximum cut, chromatic number, hamiltonian cycle, and edge dominating set are known to be fixed-parameter tractable (FPT) when parameterized by the treewidth of the input graphs, but become W-hard with respect to the clique-width parameter. Recently, Gajarský et al. proposed a new parameter called modular-width using the notion of modular decomposition of graphs. They showed that the chromatic number problem and the partitioning into paths problem, and hence hamiltonian path and hamiltonian cycle, are FPT when parameterized by this parameter. In this paper, we study modular-width in parameterized parallel complexity and show that the weighted maximum clique problem and the maximum matching problem are fixed-parameter parallel-tractable (FPPT) when parameterized by this parameter. AU - Abu-Khzam, Faisal N. AU - Li, Shouwei AU - Markarian, Christine AU - Meyer auf der Heide, Friedhelm AU - Podlipyan, Pavel ID - 82 T2 - Proceedings of the 11th International Workshop on Frontiers in Algorithmics (FAW) TI - Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity 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 AU - Podlipyan, Pavel AU - Li, Shouwei AU - Markarian, Christine AU - Meyer auf der Heide, Friedhelm ID - 16349 T2 - Proceedings of the 13th International Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS) TI - A Continuous Strategy for Collisionless Gathering ER - TY - CONF AB - Efficiently parallelizable parameterized problems have been classified as being either in the class FPP (fixed-parameter parallelizable) or the class PNC (parameterized analog of NC), which contains FPP as a subclass. In this paper, we propose a more restrictive class of parallelizable parameterized problems called fixed-parameter parallel-tractable (FPPT). For a problem to be in FPPT, it should possess an efficient parallel algorithm not only from a theoretical standpoint but in practice as well. The primary distinction between FPPT and FPP is the parallel processor utilization, which is bounded by a polynomial function in the case of FPPT. We initiate the study of FPPT with the well-known k-vertex cover problem. In particular, we present a parallel algorithm that outperforms the best known parallel algorithm for this problem: using O(m) instead of O(n2) parallel processors, the running time improves from 4logn+O(kk) to O(k⋅log3n), where m is the number of edges, n is the number of vertices of the input graph, and k is an upper bound of the size of the sought vertex cover. We also note that a few P-complete problems fall into FPPT including the monotone circuit value problem (MCV) when the underlying graphs are bounded by a constant Euler genus. AU - Abu-Khzam, Faisal N. AU - Li, Shouwei AU - Markarian, Christine AU - Meyer auf der Heide, Friedhelm AU - Podlipyan, Pavel ID - 177 T2 - Proceedings of the 10th International Conference on Combinatorial Optimization and Applications (COCOA) TI - On the Parameterized Parallel Complexity and the Vertex Cover Problem ER - TY - JOUR AB - 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). AU - Abshoff, Sebastian AU - Kling, Peter AU - Markarian, Christine AU - Meyer auf der Heide, Friedhelm AU - Pietrzyk, Peter ID - 139 IS - 4 JF - Journal of Combinatorial Optimization TI - Towards the price of leasing online ER - TY - CONF AB - We present an efficient parallel algorithm for the general Monotone Circuit Value Problem (MCVP) with n gates and an underlying graph of bounded genus k. Our algorithm generalizes a recent result by Limaye et al. who showed that MCVP with toroidal embedding (genus 1) is in NC when the input contains a toroidal embedding of the circuit. In addition to extending this result from genus 1 to any bounded genus k, and unlike the work reported by Limaye et al., we do not require a precomputed embedding to be given. Most importantly, our results imply that given a P-complete problem, it is possible to find an algorithm that makes the problem fall into NC by fixing one or more parameters. Hence, we deduce the interesting analogy: Fixed Parameter Parallelizable (FPP) is with respect to P-complete what Fixed Parameter Tractable (FPT) is with respect to NP-complete. Similar work that uses treewidth as parameter was also presented by Elberfeld et al. in [6]. AU - Abu-Khzam, Faisal N. AU - Li, Shouwei AU - Markarian, Christine AU - Meyer auf der Heide, Friedhelm AU - Podlipyan, Pavel ID - 143 T2 - Proceedings of the 22nd International Conference on Computing and Combinatorics (COCOON) TI - The Monotone Circuit Value Problem with Bounded Genus Is in NC ER - TY - CONF AB - Many markets have seen a shift from the idea of buying and moved to leasing instead. Arguably, the latter has been the major catalyst for their success. Ten years ago, research realized this shift and initiated the study of "online leasing problems" by introducing leasing to online optimization problems. Resources required to provide a service in an "online leasing problem" are no more bought but leased for different durations. In this paper, we provide an overview of results that contribute to the understanding of "online resource leasing problems". AU - Markarian, Christine AU - Meyer auf der Heide, Friedhelm ID - 266 T2 - Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC) TI - Online Resource Leasing ER - TY - THES AU - Markarian, Christine ID - 267 TI - Online Resource Leasing ER - TY - CONF AB - We consider online leasing problems in which demands arrive over time and need to be served by leasing resources. We introduce a new model for these problems such that a resource can be leased for K different durations each incurring a different cost (longer leases cost less per time unit). Each demand i can be served anytime between its arrival ai and its deadline ai+di by a leased resource. The objective is to meet all deadlines while minimizing the total leasing costs. This model is a natural generalization of Meyerson’s ParkingPermitProblem (FOCS 2005) in which di=0 for all i. We propose an online algorithm that is Θ(K+dmaxlmin)-competitive where dmax and lmin denote the largest di and the shortest available lease length, respectively. We also extend the SetCoverLeasing problem by deadlines and give a competitive online algorithm which also improves on existing solutions for the original SetCoverLeasing problem. AU - Li, Shouwei AU - Mäcker, Alexander AU - Markarian, Christine AU - Meyer auf der Heide, Friedhelm AU - Riechers, Sören ID - 240 T2 - Proceedings of the 21st Annual International Computing and Combinatorics Conference (COCOON) TI - Towards Flexible Demands in Online Leasing Problems ER - TY - GEN AB - We consider the problem of dominating set-based virtual backbone used for routing in asymmetric wireless ad-hoc networks. These networks have non-uniform transmission ranges and are modeled using the well-established disk graphs. The corresponding graph theoretic problem seeks a strongly connected dominating-absorbent set of minimum cardinality in a digraph. A subset of nodes in a digraph is a strongly connected dominating-absorbent set if the subgraph induced by these nodes is strongly connected and each node in the graph is either in the set or has both an in-neighbor and an out-neighbor in it. Distributed algorithms for this problem are of practical significance due to the dynamic nature of ad-hoc networks. We present a first distributed approximation algorithm, with a constant approximation factor and O(Diam) running time, where Diam is the diameter of the graph. Moreover we present a simple heuristic algorithm and conduct an extensive simulation study showing that our heuristic outperforms previously known approaches for the problem. AU - Abu-Khzam, Faisal N. AU - Markarian, Christine AU - Meyer auf der Heide, Friedhelm AU - Schubert, Michael ID - 16452 T2 - arXiv:1510.01866 TI - Approximation and Heuristic Algorithms for Computing Backbones in Asymmetric Ad-Hoc Networks ER - TY - CONF AB - 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. AU - Abshoff, Sebastian AU - Markarian, Christine AU - Meyer auf der Heide, Friedhelm ID - 379 T2 - Proceedings of the 8th Annual International Conference on Combinatorial Optimization and Applications (COCOA) TI - Randomized Online Algorithms for Set Cover Leasing Problems ER - TY - CONF AB - In this survey article, we discuss two algorithmic research areas that emerge from problems that arise when resources are offered in the cloud. The first area, online leasing, captures problems arising from the fact that resources in the cloud are not bought, but leased by cloud vendors. The second area, Distributed Storage Systems, deals with problems arising from so-called cloud federations, i.e., when several cloud providers are needed to fulfill a given task. AU - Kniesburges, Sebastian AU - Markarian, Christine AU - Meyer auf der Heide, Friedhelm AU - Scheideler, Christian ID - 459 T2 - Proceedings of the 21st International Colloquium on Structural Information and Communication Complexity (SIROCCO) TI - Algorithmic Aspects of Resource Management in the Cloud ER - TY - CONF AB - Dominating set based virtual backbones are used for rou-ting in wireless ad-hoc networks. Such backbones receive and transmit messages from/to every node in the network. Existing distributed algorithms only consider undirected graphs, which model symmetric networks with uniform transmission ranges. We are particularly interested in the well-established disk graphs, which model asymmetric networks with non-uniform transmission ranges. The corresponding graph theoretic problem seeks a strongly connected dominating-absorbent set of minimum cardinality in a digraph. A subset of nodes in a digraph is a strongly connected dominating-absorbent set if the subgraph induced by these nodes is strongly connected and each node in the graph is either in the set or has both an in-neighbor and an out-neighbor in it. We introduce the first distributed algorithm for this problem in disk graphs. The algorithm gives an O(k^4) -approximation ratio and has a runtime bound of O(Diam) where Diam is the diameter of the graph and k denotes the transmission ratio r_{max}/r_{min} with r_{max} and r_{min} being the maximum and minimum transmission range, respectively. Moreover, we apply our algorithm on the subgraph of disk graphs consisting of only bidirectional edges. Our algorithm gives an O(ln k) -approximation and a runtime bound of O(k^8 log^∗ n) , which, for bounded k , is an optimal approximation for the problem, following Lenzen and Wattenhofer’s Ω(log^∗ n) runtime lower bound for distributed constant approximation in disk graphs. AU - Markarian, Christine AU - Meyer auf der Heide, Friedhelm AU - Schubert, Michael ID - 563 T2 - Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS) TI - A Distributed Approximation Algorithm for Strongly Connected Dominating-Absorbent Sets in Asymmetric Wireless Ad-Hoc Networks ER -