A5049579750- Optimization and Search Problems
- Advanced Graph Theory Research
- Complexity and Algorithms in Graphs
- Interconnection Networks and Systems
- Advanced Optical Network Technologies
- Mobile Ad Hoc Networks
- Scheduling and Optimization Algorithms
- Computational Geometry and Mesh Generation
- graph theory and CDMA systems
- Cooperative Communication and Network Coding
- Opportunistic and Delay-Tolerant Networks
- Optical Network Technologies
- Mobile Agent-Based Network Management
- Network Traffic and Congestion Control
- Distributed and Parallel Computing Systems
- Advanced Bandit Algorithms Research
- Algorithms and Data Compression
- Optimization and Packing Problems
- Energy Efficient Wireless Sensor Networks
- Machine Learning and Algorithms
- Internet Traffic Analysis and Secure E-voting
- Wireless Networks and Protocols
- Advanced Wireless Network Optimization
- Transportation and Mobility Innovations
- Auction Theory and Applications
Durham University
2022-2024
Kadir Has University
2023
University of Leicester
2012-2021
Technische Hochschule Mittelhessen
2021
Bahria University
2013
ETH Zurich
2000-2006
University of Liverpool
2006
Board of the Swiss Federal Institutes of Technology
2003-2004
École Polytechnique Fédérale de Lausanne
2002
Technical University of Munich
1997-2001
<para xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> Due to its fast, dynamic, and distributed growth process, it is hard obtain an accurate map of the Internet. In many cases, such a map—representing structure Internet as graph with nodes links—is prerequisite when investigating properties A common way maps make certain local measurements at small subset nodes, then combine these in order "discover" (an approximation of) actual graph. Each...
A disk graph is the intersection of a set disks with arbitrary diameters in plane. For case that representation given, we present polynomial-time approximation schemes (PTASs) for maximum weight independent problem (selecting disjoint total weight) and minimum vertex cover graphs. These are first known PTASs $\mathcal{NP}$-hard optimization problems on They based novel recursive subdivision plane allows applying shifting strategy different levels simultaneously, so dynamic programming...
A disk graph is the intersection of a set disks with arbitrary diameters in plane. For case that representation given, we present polynomial-time approximation schemes (PTASs) for maximum weight independent problem (selecting disjoint total weight) and minimum vertex cover graphs. These are first known PTASs NP-hard optimization problems on They based novel recursive subdivision plane allows applying shifting strategy different levels simultaneously, so dynamic programming approach becomes...
For multiobjective optimization problems, it is meaningful to compute a set of solutions covering all possible trade-offs between the different objectives. The knapsack problem generalization classical in which each item has several profit values. this problem, efficient algorithms for computing provably good approximation nondominated feasible solutions, Pareto frontier, are studied. one-dimensional practical fully polynomial-time scheme (FPTAS) derived. It based on new approach...
A virtual private network (VPN) provides connections over a publicly accessible shared network. Bandwidth provisioning for VPNs leads to challenging optimization problems. In the hose model proposed by Duffield et al., each VPN endpoint specifies bounds on total amount of traffic that it will send or receive at any time. The provider must provision so there is sufficient bandwidth matrix consistent with these bounds. While previous work has considered tree routing and single-path between...
We investigate the problem of computing types relationships between Internet Autonomous Systems. refer to model introduced by Gao [IEEE/ACM Transactions on Networking, 9(6):733-645, 2001] and Subramanian (IEEE Infocom, 2002) that bases discovery such analysis AS paths extracted from BGP routing tables. characterize time complexity above problem, showing both NP-completeness results efficient algorithms for solving specific cases. Motivated hardness general we propose approximation heuristics...
For a given number L , an -length-bounded edge-cut (node-cut, respectively) in graph G with source s and sink t is set C of edges (nodes, such that no - -path length at most remains the after removing . An flow can be decomposed into paths In contrast to classical theory, we describe instances for which minimum Θ( n 2/3 )-times (Θ(√ )-times, larger than maximum flow, where denotes nodes; this worst case. We show length-bounded cut problem NP -hard approximate within factor 1.1377 ≥ 5 case...
The problem of establishing and completing a given set calls as early possible is studied for bidirectional directed in various classes networks. Even under the assumption unit bandwidth requirements call durations, scheduling NP-hard trees with unbounded degree, rings, meshes. Whereas can be scheduled optimally polynomial time constant already binary trees. Approximation algorithms performance ratio are known many variants scheduling.
We consider the minimum spanning tree problem in a setting where information about edge weights of given graph is uncertain. Initially, for each $e$ only set $A_e$, called an uncertainty area, that contains actual weight $w_e$ known. The algorithm can `update' to obtain $w_e \in A_e$. task output after number updates. An $k$-update competitive if it makes at most $k$ times as many updates optimum. present 2-update all areas $A_e$ are open or trivial, which best possible among deterministic...
We consider the version of broadcast scheduling where a server can transmit one message given set at each time-step, answering previously made requests for that message. The goal is to minimize average response time if amount known in advance time-step and prove this problem NP-hard, thus an open question stated by Kalyanasundaram, Pruhs Velauthapillai (Proceedings ESA 2000, LNCS 1879, pp. 290-301). Furthermore, we present approximation algorithm allowed send several messages once. Using 6...