A5041355842- Complexity and Algorithms in Graphs
- Optimization and Search Problems
- Advanced Graph Theory Research
- Vehicle Routing Optimization Methods
- Optimization and Packing Problems
- Computational Geometry and Mesh Generation
- Scheduling and Optimization Algorithms
- Formal Methods in Verification
- Cryptography and Data Security
- Caching and Content Delivery
- Digital Image Processing Techniques
- VLSI and FPGA Design Techniques
- Advanced Manufacturing and Logistics Optimization
- semigroups and automata theory
- Algorithms and Data Compression
- DNA and Biological Computing
- Genome Rearrangement Algorithms
- Auction Theory and Applications
- Machine Learning and Algorithms
- Graph Labeling and Dimension Problems
- Constraint Satisfaction and Optimization
- Smart Parking Systems Research
- Facility Location and Emergency Management
- Metaheuristic Optimization Algorithms Research
- Gene expression and cancer classification
University of Augsburg
2021-2025
Saarland University
2013-2020
University of Bremen
2018
KTH Royal Institute of Technology
2010-2012
ETH Zurich
2006-2011
We present a framework for approximating the metric TSP based on novel use of matchings. Traditionally, matchings have been used to add edges make given graph Eulerian, whereas our approach also allows removal certain leading decreased cost. For graphic metrics (graph-TSP), we show that gives 1.461-approximation algorithm with respect Held-Karp lower bound. graph-TSP restricted either half-integral solutions relaxation or class graphs contains subcubic and claw-free graphs, integrality gap...
We investigate semi-streaming algorithms for the Traveling Salesman Problem (TSP). Specifically, we focus on a variant known as $(1,2)$-TSP, where distances between any two vertices are either one or two. Our primary emphasis is closely related Maximum Path Cover Problem, which aims to find collection of vertex-disjoint paths that covers maximum number edges in graph. propose an algorithm that, $\epsilon > 0$, achieves $(\frac{2}{3}-\epsilon)$-approximation path cover size $n$-vertex graph,...
We study the unsplittable flow on a path problem which has received lot of attention in research community recently. Given is with capacities its edges and set tasks where each task characterized by source sink vertex, demand, profit. The goal to find subset maximum total profit such that all demands from this can be routed simultaneously without violating capacity constraints. best known approximation results are quasi-polynomial time-approximation scheme if range [Bansal et al., STOC 2006]...
We study the unsplittable flow on a path problem which has received lot of attention in research community recently. Given is with capacities its edges and set tasks where each task characterized by source sink vertex, demand, profit. The goal to find subset maximum total profit such that all demands from this can be routed simultaneously without violating capacity constraints. best known approximation results are quasi-polynomial time-approximation scheme if range [Bansal et al., STOC 2006]...
In the unsplittable flow on a path problem (UFP) we are given with edge capacities and collection of tasks. Each task is characterized by subpath, profit, demand. Our goal to compute maximum profit subset tasks such that, for each e, total demand selected that use e does not exceed capacity e. The current best polynomial-time approximation factor this 2+є any constant є>0 [Anagostopoulos et al.-SODA 2014]. This known even in case uniform [Călinescu al.-IPCO 2002, TALG 2011]. These results,...
Size and weight limitations of low-earth orbit (LEO) small satellites make their operation rest on a fine balance between solar power infeed demands communication technologies board, buffered by on-board battery storage. As result, the problem planning battery-powered payload utilization together with intersatellite is extremely intricate. Nevertheless, there growing trend toward constellations megaconstellations that are to be managed using sophisticated software support. Earlier work has...