A5042072430- Constraint Satisfaction and Optimization
- Complexity and Algorithms in Graphs
- Logic, Reasoning, and Knowledge
- Auction Theory and Applications
- Game Theory and Voting Systems
- Advanced Graph Theory Research
- Data Management and Algorithms
- Rough Sets and Fuzzy Logic
- Interconnection Networks and Systems
- Formal Methods in Verification
- Bayesian Modeling and Causal Inference
- Optimization and Search Problems
- Smart Parking Systems Research
- Transportation and Mobility Innovations
- Metaheuristic Optimization Algorithms Research
- Vehicle Routing Optimization Methods
- Distributed and Parallel Computing Systems
- Mobile Ad Hoc Networks
- Advanced Multi-Objective Optimization Algorithms
- Urban Transport and Accessibility
- Semantic Web and Ontologies
- Transportation Planning and Optimization
- Complex Network Analysis Techniques
- Scheduling and Timetabling Solutions
- Scheduling and Optimization Algorithms
University of Potsdam
2018-2023
Hasso Plattner Institute
2017-2023
Friedrich Schiller University Jena
2015-2016
We investigate the performance of a deterministic GREEDY algorithm for problem maximizing functions under partition matroid constraint. consider non-monotone submodular and monotone subadditive functions. Even though constrained maximization problems have been extensively studied, little is known about greedy or functions.
 give approximation guarantees on these problems, in terms curvature. find that this simple heuristic yields strong guarantee broad class discuss applicability our...
Recently, a number of non-uniform random satisfiability models have been proposed that are closer to practical problems in some characteristics. In contrast uniform Boolean formulas, scale-free formulas variable occurrence distribution follows power law. It has conjectured such is more accurate model for industrial instances than the model. Though it seems there already an awareness threshold phenomenon models, still complete picture lacking. model, critical density does not lie at single...
Computing diverse solutions for a given problem, in particular evolutionary diversity optimisation (EDO), is hot research topic the computation community. This paper studies Boolean satisfiability problem (SAT) context of EDO. SAT great importance computer science and differs from other problems studied EDO literature, such as KP TSP. heavily constrained, conventional operators are inefficient generating solutions. Our approach avails following characteristics SAT: 1) possibility adding more...
A significant percentage of urban traffic is caused by the search for parking spots. One possible approach to improve this situation guide drivers along routes which are likely have free The task finding such a route can be modeled as probabilistic graph problem i s NP-complete. Thus, we propose heuristic approaches solving and evaluate them experimentally. For this, use probabilities spot, based on publicly available empirical data from TomTom International B.V. Additionally, that relies...
Propositional satisfiability (SAT) is one of the most fundamental problems in computer science. The worst-case hardness SAT lies at core computational complexity theory. average-case analysis has triggered development sophisticated rigorous and non-rigorous techniques for analyzing random structures. Despite a long line research substantial progress, nearly all theoretical work on assumes uniform distribution variables. In contrast, real-world instances often exhibit large fluctuations...
An estimated 30% of urban traffic is caused by search for parking spots [Shoup, 2005]. Suggesting routes along highly probable could reduce traffic. In this paper, we formalize as a probabilistic problem on road graph and show that it NP-complete. We explore heuristics optimize the driving duration walking distance to destination. Routes are constrained reach certain probability threshold finding spot. Empirically probabilities successful attempts provided TomTom per-street basis. release...
Assigning staff to engagements according hard constraints while optimizing several objectives is a task encountered by many companies on regular basis. Simplified versions of such assignment problems are NP-hard. Despite this, typical approach solving them consists formulating as mixed integer programming (MIP) and using stateof-the-art solver get solutions that closely approximate the optimum.In this paper, we consider complex real-world problem professional service company KPMG, with goal...
Propositional satisfiability (SAT) is one of the most fundamental problems in computer science. Its worst-case hardness lies at core computational complexity theory, for example form NP-hardness and (Strong) Exponential Time Hypothesis. In practice however, SAT instances can often be solved efficiently. This contradicting behavior has spawned interest average-case analysis triggered development sophisticated rigorous non-rigorous techniques analyzing random structures. Despite a long line...
Large real-world networks typically follow a power-law degree distribution. To study such networks, numerous random graph models have been proposed. However, are not drawn at random. In fact, the behavior of and can be complete opposite one another, depending on considered property. Brach, Cygan, Lacki, Sankowski [SODA 2016] introduced two natural deterministic conditions: (1) upper bound distribution (PLB-U) (2) neighborhoods, that is, neighbors each vertex is also bounded by power law...
Abstract Large real-world networks typically follow a power-law degree distribution. To study such networks, numerous random graph models have been proposed. However, are not drawn at random. Therefore, Brach et al. (27th symposium on discrete algorithms (SODA), pp 1306–1325, 2016) introduced two natural deterministic conditions: (1) upper bound the distribution (PLB-U) and (2) neighborhoods, that is, of neighbors each vertex is also bounded by power law (PLB-N). They showed many satisfy...
Abstract Satisfiability is considered the canonical NP‐complete problem and used as a starting point for hardness reductions in theory, while practice heuristic SAT solving algorithms can solve large‐scale industrial instances very efficiently. This disparity between theory believed to be result of inherent properties that make them tractable. Two characteristic seem prevalent majority real‐world instances, heterogeneous degree distribution locality. To understand impact these two on SAT, we...
We study a more general model to generate random instances of Propositional Satisfiability (SAT) with n Boolean variables, m clauses, and exactly k variables per clause. Additionally, our is given an arbitrary probability distribution (p_1, ..., p_n) on the variable occurrences. Therefore, we call it non-uniform k-SAT. The number randomly drawn clauses at which formulas go from asymptotically almost surely (a.a.s.) satisfiable a.a.s. unsatisfiable called satisfiability threshold. Such...
Modern routing algorithms reduce query time by depending heavily on preprocessed data. The recently developed Navigation Data Standard (NDS) enforces a separation between and map data, rendering preprocessing inapplicable. Furthermore, data is partitioned into tiles with respect to their geographic coordinates. With the limited memory found in portable devices, number of loaded becomes major factor for run time. We study under these restrictions present new as well empirical evaluations. Our...
We investigate the performance of a deterministic GREEDY algorithm for problem maximizing functions under partition matroid constraint. consider non-monotone submodular and monotone subadditive functions. Even though constrained maximization problems have been extensively studied, little is known about greedy or give approximation guarantees on these problems, in terms curvature. find that this simple heuristic yields strong guarantee broad class discuss applicability our results to three...
The “HPI Future SOC Lab” is a cooperation of the Hasso Plattner Institute (HPI) and industry partners. Its mission to enable promote exchange interaction between research community partners. HPI Lab provides researchers with free charge access complete infrastructure state art hard software. This includes components, which might be too expensive for an ordinary environment, such as servers up 64 cores 2 TB main memory. offerings address particularly from but not limited areas computer...
Satisfiability is considered the canonical NP-complete problem and used as a starting point for hardness reductions in theory, while practice heuristic SAT solving algorithms can solve large-scale industrial instances very efficiently. This disparity between theory believed to be result of inherent properties that make them tractable. Two characteristic seem prevalent majority real-world instances, heterogeneous degree distribution locality. To understand impact these two on SAT, we study...