AKAthanasios L. Konstantinidis
Athanasios L. Konstantinidis
*This is an algorithmically generated author record based on publicly available information.
Athanasios L. Konstantinidis has a total of 8 co-authors. Here are the top co-authors by number of shared publications:
- Giuseppe Francesco Italiano
Luiss University, Rome, Italy
4 shared publications - Charis Papadopoulos
Department of Mathematics University of Ioannina Greece
1 shared publication - Evangelos Kosinas
Department of Computer Science & Engineering University of Ioannina Greece
1 shared publication - Lutz Oettershagen
KTH Royal Institute of Technology, Stockholm, Sweden
1 shared publication - Lutz Oettershagen
KTH Royal Institute of Technology Luiss University Italiano Luiss University
1 shared publication - Manas Jyoti Kashyop
Indian Institute of Technology Madras
1 shared publication
Latest Publications
- Open Access
Online Drone Scheduling for Last-mile Delivery
Delivering a parcel from the distribution hub to the customer's doorstep is called the \textit{last-mile delivery} step in delivery logistics. In this paper, we study a hybrid {\it truck-drones} model for the last-mile delivery step, in which a truck moves on a predefined path carrying parcels and drones deliver the parcels. We define the \textsc{online drone scheduling} problem, where the truck moves in a predefined path, and the customer's requests appear online during the truck's movement. The objective is to schedule a drone associated with every request to minimize the number of drones used subject to the battery budget of the drones and compatibility of the schedules. We propose a 3-competitive deterministic algorithm using the next-fit strategy and 2.7-competitive algorithms using the first-fit strategy for the problem with $O(\log n)$ worst-case time complexity per request, where $n$ is the maximum number of active requests at any time. We also introduce \textsc{online variable-size drone scheduling} problem (OVDS). Here, we know all the customer's requests in advance; however, the drones with different battery capacities appear online. The objective is to schedule customers' requests for drones to minimize the number of drones used. We propose a $(2α+ 1)$-competitive algorithm for the OVDS problem with total running time $O(n \log n)$ for $n$ customer requests, where $α$ is the ratio of the maximum battery capacity to the minimum battery capacity of the drones. Finally, we address how to generate intervals corresponding to each customer request when there are discrete stopping points on the truck's route, from where the drone can fly and meet with the truck.Open AccessOnline Drone Scheduling for Last-mile Delivery
Delivering a parcel from the distribution hub to the customer's doorstep is called the \textit{last-mile delivery} step in delivery logistics. In this paper, we study a hybrid {\it truck-drones} model for the last-mile delivery step, in which a truck moves on a predefined path carrying parcels and drones deliver the parcels. We define the \textsc{online drone scheduling} problem, where the truck moves in a predefined path, and the customer's requests appear online during the truck's movement. The objective is to schedule a drone associated with every request to minimize the number of drones used subject to the battery budget of the drones and compatibility of the schedules. We propose a 3-competitive deterministic algorithm using the next-fit strategy and 2.7-competitive algorithms using the first-fit strategy for the problem with $O(\log n)$ worst-case time complexity per request, where $n$ is the maximum number of active requests at any time. We also introduce \textsc{online variable-size drone scheduling} problem (OVDS). Here, we know all the customer's requests in advance; however, the drones with different battery capacities appear online. The objective is to schedule customers' requests for drones to minimize the number of drones used. We propose a $(2α+ 1)$-competitive algorithm for the OVDS problem with total running time $O(n \log n)$ for $n$ customer requests, where $α$ is the ratio of the maximum battery capacity to the minimum battery capacity of the drones. Finally, we address how to generate intervals corresponding to each customer request when there are discrete stopping points on the truck's route, from where the drone can fly and meet with the truck. - Open Access
Inferring Tie Strength in Temporal Networks
Inferring tie strengths in social networks is an essential task in social network analysis. Common approaches classify the ties as wea} and strong ties based on the strong triadic closure (STC). The STC states that if for three nodes, $A$, $B$, and $C$, there are strong ties between $A$ and $B$, as well as $A$ and $C$, there has to be a (weak or strong) tie between $B$ and $C$. A variant of the STC called STC+ allows adding a few new weak edges to obtain improved solutions. So far, most works discuss the STC or STC+ in static networks. However, modern large-scale social networks are usually highly dynamic, providing user contacts and communications as streams of edge updates. Temporal networks capture these dynamics. To apply the STC to temporal networks, we first generalize the STC and introduce a weighted version such that empirical a priori knowledge given in the form of edge weights is respected by the STC. Similarly, we introduce a generalized weighted version of the STC+. The weighted STC is hard to compute, and our main contribution is an efficient 2-approximation (resp. 3-approximation) streaming algorithm for the weighted STC (resp. STC+) in temporal networks. As a technical contribution, we introduce a fully dynamic $k$-approximation for the minimum weighted vertex cover problem in hypergraphs with edges of size $k$, which is a crucial component of our streaming algorithms. An empirical evaluation shows that the weighted STC leads to solutions that better capture the a priori knowledge given by the edge weights than the non-weighted STC. Moreover, we show that our streaming algorithm efficiently approximates the weighted STC in real-world large-scale social networks.Open AccessInferring Tie Strength in Temporal Networks
Inferring tie strengths in social networks is an essential task in social network analysis. Common approaches classify the ties as wea} and strong ties based on the strong triadic closure (STC). The STC states that if for three nodes, $A$, $B$, and $C$, there are strong ties between $A$ and $B$, as well as $A$ and $C$, there has to be a (weak or strong) tie between $B$ and $C$. A variant of the STC called STC+ allows adding a few new weak edges to obtain improved solutions. So far, most works discuss the STC or STC+ in static networks. However, modern large-scale social networks are usually highly dynamic, providing user contacts and communications as streams of edge updates. Temporal networks capture these dynamics. To apply the STC to temporal networks, we first generalize the STC and introduce a weighted version such that empirical a priori knowledge given in the form of edge weights is respected by the STC. Similarly, we introduce a generalized weighted version of the STC+. The weighted STC is hard to compute, and our main contribution is an efficient 2-approximation (resp. 3-approximation) streaming algorithm for the weighted STC (resp. STC+) in temporal networks. As a technical contribution, we introduce a fully dynamic $k$-approximation for the minimum weighted vertex cover problem in hypergraphs with edges of size $k$, which is a crucial component of our streaming algorithms. An empirical evaluation shows that the weighted STC leads to solutions that better capture the a priori knowledge given by the edge weights than the non-weighted STC. Moreover, we show that our streaming algorithm efficiently approximates the weighted STC in real-world large-scale social networks.