A5000044334- Auction Theory and Applications
- Game Theory and Applications
- Advanced Graph Theory Research
- Game Theory and Voting Systems
- Complexity and Algorithms in Graphs
- Advanced Authentication Protocols Security
- Formal Methods in Verification
- semigroups and automata theory
- Web Application Security Vulnerabilities
- Vehicle Routing Optimization Methods
- Optimization and Search Problems
- Logic, programming, and type systems
- Cryptography and Data Security
- Software Testing and Debugging Techniques
- Access Control and Trust
- Point processes and geometric inequalities
- User Authentication and Security Systems
- Supply Chain and Inventory Management
- Advanced Combinatorial Mathematics
- Caching and Content Delivery
- Scheduling and Optimization Algorithms
- Computational Geometry and Mesh Generation
- Operations Management Techniques
University of Stuttgart
2024
Technical University of Munich
2016-2022
In this paper we report on the full classification of Dirichlet-Voronoi polyhedra and Delaunay subdivisions five-dimensional translational lattices. We obtain a complete list $110244$ affine types (L-types) it turns out that they are all combinatorially inequivalent, giving same number combinatorial polyhedra. Using refinement corresponding secondary cones, $181394$ contraction types. details our computer assisted enumeration, which verified by three independent implementations topological...
Abstract Transforming $$\omega $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ω</mml:mi> </mml:math> -automata into parity automata is traditionally done using appearance records. We present an efficient variant of this idea, tailored to Rabin automata, and several optimizations applicable all compare the methods experimentally show that our method produces significantly smaller than previous approaches.
We study the existence of approximate pure Nash equilibria (α-PNE) in weighted atomic congestion games with polynomial cost functions maximum degree d. Previously it was known that d-approximate always exist, while nonexistence established only for small constants, namely 1.153-PNE. improve significantly upon this gap, proving such general do not have Θ(√d)-approximate PNE, which provides first super-constant lower bound. Furthermore, we provide a black-box gap-introducing method combining...
The $k$ disjoint shortest paths problem ($k$-DSPP) on a graph with source-sink pairs $(s_i, t_i)$ asks for the existence of pairwise edge- or vertex-disjoint $s_i$-$t_i$-paths. It is known to be NP-complete if part input. Restricting $2$-DSPP strictly positive lengths, it becomes solvable in polynomial time. We extend this result by allowing zero edge lengths and give time algorithm based dynamic programming undirected graphs non-negative lengths.
Budget Minimization is a scheduling problem with precedence constraints, i.e., on partially ordered set of jobs $(N, \unlhd)$. A job $j \in N$ available for scheduling, if all $i \unlhd j$ are completed. Further, each assigned real valued costs $c_{j}$, which can be negative or positive. schedule an ordering $j_{1}, \dots, j_{\vert N \vert}$ in $N$. The budget the external investment needed to complete jobs, it $\max_{l \{0, \vert \} } \sum_{1 \le k l} c_{j_{k}}$. goal find minimum budget....
We study the existence of approximate pure Nash equilibria ($\alpha$-PNE) in weighted atomic congestion games with polynomial cost functions maximum degree $d$. Previously it was known that $d$-approximate always exist, while nonexistence established only for small constants, namely $1.153$-PNE. improve significantly upon this gap, proving such general do not have $\tilde{\Theta}(\sqrt{d})$-approximate PNE, which provides first super-constant lower bound. Furthermore, we provide a black-box...
We study the existence of approximate pure Nash equilibria (α-PNE) in weighted atomic congestion games with polynomial cost functions maximum degree d. Previously, it was known that d-PNE always exist, whereas nonexistence established only for small constants, namely, 1.153-PNE. improve significantly upon this gap, proving such general do not have [Formula: see text]-PNE, which provides first superconstant lower bound. Furthermore, we provide a black-box gap-introducing method combining...