### Integrating Passengers' Assignment in Cost-Optimal Line Planning

Markus Friedrich, Maximilian Hartl, Alexander Schiewe & Anita Schöbel
Finding a line plan with corresponding frequencies is an mportant stage of planning a public transport system. A line plan should permit all passengers to travel with an appropriate quality at appropriate costs for the public transport operator. Traditional line planning procedures proceed sequentially: In a first step a traffic assignment allocates passengers to routes in the network, often by means of a shortest path assignment. The resulting traffic loads are used in a second...

### Routing in Polygonal Domains

Bahareh Banyassady, Man-Kwun Chiu, Matias Korman, Wolfgang Mulzer, André Van Renssen, Marcel Roeloffzen, Paul Seiferth, Yannik Stein, Birgit Vogtenhuber & Max Willert
We consider the problem of routing a data packet through the visibility graph of a polygonal domain P with n vertices and h holes. We may preprocess P to obtain a label and a routing table for each vertex. Then, we must be able to route a data packet between any two vertices p and q of P , where each step must use only the label of the target node q and the routing...

### Monitor Logics for Quantitative Monitor Automata

Erik Paul
We introduce a new logic called Monitor Logic and show that it is expressively equivalent to Quantitative Monitor Automata.

### Symbolic-Numeric Methods for Problem Solving in CPS (Dagstuhl Seminar 16491)

Sergiy Bogomolov, Martin Fränzle, Kyoko Makino & Nacim Ramdani
Reflecting the fundamental role numeric and mixed symbolic-numeric arguments play in the analysis, decision making, and control of cyber-physical processes, this seminar promoted cross-fertilization between the following research areas relevant to problem solving in cyber-physical domains: verification of numerical reactive systems such as embedded floating-point programs and hybrid systems, including novel means of error-propagation analysis; numerical and/or symbolic methods such as verified integrations, interval methods and arithmetic constraint solving; reactive and in-advance planning and optimization...

### On Decidability of Concurrent Kleene Algebra

Paul Brunet, Damien Pous & Georg Struth
Concurrent Kleene algebras support equational reasoning about computing systems with concurrent behaviours. Their natural semantics is given by series(-parallel) rational pomset languages, a standard true concurrency semantics, which is often associated with processes of Petri nets. We use constructions on Petri nets to provide two decision procedures for such pomset languages motivated by the equational and the refinement theory of concurrent Kleene algebra. The contribution to the first problem lies in a much simpler algorithm...

### Lempel-Ziv Compression in a Sliding Window

Philip Bille, Patrick Hagge Cording, Johannes Fischer & Inge Li Gørtz
We present new algorithms for the sliding window Lempel-Ziv (LZ77) problem and the approximate rightmost LZ77 parsing problem. Our main result is a new and surprisingly simple algorithm that computes the sliding window LZ77 parse in O(w) space and either O(n) expected time or O(n log log w+z log log s) deterministic time. Here, w is the window size, n is the size of the input string, z is the number of phrases in the...

### Declutter and Resample: Towards Parameter Free Denoising

Mickael Buchet, Tamal K. Dey, Jiayuan Wang & Yusu Wang
In many data analysis applications the following scenario is commonplace: we are given a point set that is supposed to sample a hidden ground truth K in a metric space, but it got corrupted with noise so that some of the data points lie far away from K creating outliers also termed as ambient noise. One of the main goals of denoising algorithms is to eliminate such noise so that the curated data lie within...

### On the Number of Ordinary Lines Determined by Sets in Complex Space

Abdul Basit, Zeev Dvir, Shubhangi Saraf & Charles Wolf
Kelly's theorem states that a set of n points affinely spanning C^3 must determine at least one ordinary complex line (a line passing through exactly two of the points). Our main theorem shows that such sets determine at least 3n/2 ordinary lines, unless the configuration has n-1 points in a plane and one point outside the plane (in which case there are at least n-1 ordinary lines). In addition, when at most n/2 points are...

### Termination in Convex Sets of Distributions

Ana Sokolova & Harald Woracek
Convex algebras, also called (semi)convex sets, are at the heart of modelling probabilistic systems including probabilistic automata. Abstractly, they are the Eilenberg-Moore algebras of the finitely supported distribution monad. Concretely, they have been studied for decades within algebra and convex geometry. In this paper we study the problem of extending a convex algebra by a single point. Such extensions enable the modelling of termination in probabilistic systems. We provide a full description of all possible...

### Fractional Coverings, Greedy Coverings, and Rectifier Networks

Dmitry Chistikov, Szabolcs Iván, Anna Lubiw & Jeffrey Shallit

### Brief Announcement: Compact Topology of Shared-Memory Adversaries

Petr Kuznetsov, Thibault Rieutord & Yuan He
The paper proposes a simple topological characterization of a large class of adversarial distributed-computing models via affine tasks: sub-complexes of the second iteration of the standard chromatic subdivision. We show that the task computability of a model in the class is precisely captured by iterations of the corresponding affine task. While an adversary is in general defined as a non-compact set of infinite runs, its affine task is just a finite subset of runs of...

### Write-Back Caches in WCET Analysis

Tobias Blaß, Sebastian Hahn & Jan Reineke
Write-back caches are a popular choice in embedded microprocessors as they promise higher performance than write-through caches. So far, however, their use in hard real-time systems has been prohibited by the lack of adequate worst-case execution time (WCET) analysis support. In this paper, we introduce a new approach to statically analyze the behavior of write-back caches. Prior work took an "eviction-focussed perspective", answering for each potential cache miss: May this miss evict a dirty cache...

### On the Complexity of Bounded Context Switching

Peter Chini, Jonathan Kolberg, Andreas Krebs, Roland Meyer & Prakash Saivasan
Bounded context switching (BCS) is an under-approximate method for finding violations to safety properties in shared-memory concurrent programs. Technically, BCS is a reachability problem that is known to be NP-complete. Our contribution is a parameterized analysis of BCS. The first result is an algorithm that solves BCS when parameterized by the number of context switches (cs) and the size of the memory (m) in O*(m^(cs)2^(cs)). This is achieved by creating instances of the easier problem...

### Streaming Periodicity with Mismatches

Funda Ergün, Elena Grigorescu, Erfan Sadeqi Azer & Samson Zhou
We study the problem of finding all k-periods of a length-n string S, presented as a data stream. S is said to have k-period p if its prefix of length n-p differs from its suffix of length n-p in at most k locations. We give a one-pass streaming algorithm that computes the k-periods of a string S using poly(k, log n) bits of space, for k-periods of length at most n/2. We also present a...

### A Family of Approximation Algorithms for the Maximum Duo-Preservation String Mapping Problem

Bartlomiej Dudek, Pawel Gawrychowski & Piotr Ostropolski-Nalewaja
In the Maximum Duo-Preservation String Mapping problem we are given two strings and wish to map the letters of the former to the letters of the latter as to maximise the number of duos. A duo is a pair of consecutive letters that is mapped to a pair of consecutive letters in the same order. This is complementary to the well-studied Minimum Common String Partition problem, where the goal is to partition the former string...

### WNetKAT: A Weighted SDN Programming and Verification Language

Kim G. Larsen, Stefan Schmid & Bingtian Xue
Programmability and verifiability lie at the heart of the software-defined networking paradigm. While OpenFlow and its match-action concept provide primitive operations to manipulate hardware configurations, over the last years, several more expressive network programming languages have been developed. This paper presents WNetKAT, the first network programming language accounting for the fact that networks are inherently weighted, and communications subject to capacity constraints (e.g., in terms of bandwidth) and costs (e.g., latency or monetary costs). WNetKAT...

### Counting Constraint Satisfaction Problems

Mark Jerrum
This chapter surveys counting Constraint Satisfaction Problems (counting CSPs, or #CSPs) and their computational complexity. It aims to provide an introduction to the main concepts and techniques, and present a representative selection of results and open problems. It does not cover holants, which are the subject of a separate chapter.

### Stochastic k-Server: How Should Uber Work?

Sina Dehghani, Soheil Ehsani, MohammadTaghi Hajiaghayi, Vahid Liaghat & Saeed Seddighin
In this paper we study a stochastic variant of the celebrated $k$-server problem. In the k-server problem, we are required to minimize the total movement of k servers that are serving an online sequence of $t$ requests in a metric. In the stochastic setting we are given t independent distributions in advance, and at every time step i a request is drawn from P_i. Designing the optimal online algorithm in such setting is NP-hard, therefore...

### Advice Automatic Structures and Uniformly Automatic Classes

Faried Abu Zaid, Erich Grädel & Frederic Reinhardt

### Rethinking Productivity in Software Engineering (Dagstuhl Seminar 17102)

Thomas Fritz, Gloria Mark, Gail C. Murphy & Thomas Zimmermann
This report documents the program and the outcomes of Dagstuhl Seminar 17102 "Rethinking Productivity in Software Engineering". In the following, we briefly summarize the goals and format of the of the seminar, before we provide insights and an outlook, including a few grand challenges, based on the results and statements collected during the seminar.

### Polymorphisms, and How to Use Them

Libor Barto, Andrei Krokhin & Ross Willard
This article describes the algebraic approach to Constraint Satisfaction Problem that led to many developments in both CSP and universal algebra. No prior knowledge of universal algebra is assumed.

### Testing Submodularity and Other Properties of Valuation Functions

Eric Blais & Abhinav Bommireddi
We show that for any constant \epsilon > 0 and p \ge 1, it is possible to distinguish functions f : \{0,1\}^n \to [0,1] that are submodular from those that are \epsilon-far from every submodular function in \ell_p distance with a constant number of queries. More generally, we extend the testing-by-implicit-learning framework of Diakonikolas et al.(2007) to show that every property of real-valued functions that is well-approximated in \ell_2 distance by a class of k-juntas...

### Parallelizing Julia with a Non-Invasive DSL

Todd A. Anderson, Hai Liu, Lindsey Kuper, Ehsan Totoni, Jan Vitek & Tatiana Shpeisman
Computational scientists often prototype software using productivity languages that offer high-level programming abstractions. When higher performance is needed, they are obliged to rewrite their code in a lower-level efficiency language. Different solutions have been proposed to address this trade-off between productivity and efficiency. One promising approach is to create embedded domain-specific languages that sacrifice generality for productivity and performance, but practical experience with DSLs points to some road blocks preventing widespread adoption. This paper proposes...

### Exact Algorithms for List-Coloring of Intersecting Hypergraphs

Khaled Elbassioni
We show that list-coloring for any intersecting hypergraph of m edges on n vertices, and lists drawn from a set of size at most k, can be checked in quasi-polynomial time (mn)^{o(k^2*log(mn))}.

### Coding in Undirected Graphs Is Either Very Helpful or Not Helpful at All

Mark Braverman, Sumegha Garg & Ariel Schvartzman
While it is known that using network coding can significantly improve the throughput of directed networks, it is a notorious open problem whether coding yields any advantage over the multicommodity flow (MCF) rate in undirected networks. It was conjectured that the answer is no. In this paper we show that even a small advantage over MCF can be amplified to yield a near-maximum possible gap. We prove that any undirected network with k source-sink pairs...

• 2017
1,326

• Text
1,301
• Software
25