Author name cluster

David Orden

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

2 author rows

AIJ Journal 2023 Journal Article

On approximating shortest paths in weighted triangular tessellations

Prosenjit Bose
Guillermo Esteban
David Orden
Rodrigo I. Silveira

We study the quality of weighted shortest paths when a continuous 2-dimensional space is discretized by a weighted triangular tessellation. In order to evaluate how well the tessellation approximates the 2-dimensional space, we study three types of shortest paths: a weighted shortest path S P w ( s, t ), which is a shortest path from s to t in the space; a weighted shortest vertex path SV P w ( s, t ), which is an any-angle shortest path; and a weighted shortest grid path SG P w ( s, t ), which is a shortest path whose edges are edges of the tessellation. Given any arbitrary weight assignment to the faces of a triangular tessellation, thus extending recent results by Bailey et al. (2021) [6], we prove upper and lower bounds on the ratios ‖ SG P w ( s, t ) ‖ ‖ S P w ( s, t ) ‖, ‖ SV P w ( s, t ) ‖ ‖ S P w ( s, t ) ‖, ‖ SG P w ( s, t ) ‖ ‖ SV P w ( s, t ) ‖, which provide estimates on the quality of the approximation. It turns out, surprisingly, that our worst-case bounds are independent of any weight assignment. Our main result is that ‖ SG P w ( s, t ) ‖ ‖ S P w ( s, t ) ‖ = 2 3 ≈ 1. 15 in the worst case, and this is tight. As a corollary, for the weighted any-angle path SV P w ( s, t ) we obtain the approximation result ‖ SV P w ( s, t ) ‖ ‖ S P w ( s, t ) ‖ ⪅ 1. 15.

Details DOI

AAMAS Conference 2017 Conference Paper

A Distributed, Multi-Agent Approach to Reactive Network Resilience

Enrique de la Hoz
Jose Manuel Gimenez-Guzman
Ivan Marsa-Maestre
Luis Cruz-Piris
David Orden

Critical network infrastructures are communication networks whose disruption can create a severe impact on other systems. Multi-agent systems have been successfully used to protect critical network infrastructures, with approaches ranging from reasoning about secure design and policies to multi-agent intrusion detection systems (IDS). However, there is little research on the possibilities for multiagent systems to react to known intrusions. In this paper we propose a multi-agent framework for reactive network resilience, that is, to allow a network to reconfigure itself in the event of a security incident so that the risk of further damage is mitigated. The proposed framework takes advantage of a risk model based on multilayer networks and of distributed belief propagation techniques to agree on a new, more resilient configuration of the network in the event of an attack. We compare our proposal with a number of centralized optimization and multi-agent negotiation techniques. Experiments show that our proposal outperforms the reference approaches both in terms of risk mitigation and performance

PDF

AAMAS Conference 2017 Conference Paper

Multi-Agent Nonlinear Negotiation for Wi-Fi Channel Assignment

Enrique de la Hoz
Ivan Marsa-Maestre
Jose Manuel Gimenez-Guzman
David Orden
Mark Klein

Optimizing resource use in complex networks with self-interested participants (e. g. transportation networks, electric grids, Internet systems) is a challenging and increasingly critical real-world problem. We propose an approach for solving this problem based on multi-agent nonlinear negotiation, and demonstrate it in the context of Wi-Fi channel assignment. We compare the performance of our proposed approaches with a complete information optimizer based on particle swarms, together with the de facto heuristic technique based on using the least congested channel. We have evaluated all these techniques in a wide range of settings, including randomly generated scenarios and real-world ones. Our experiments show that our approach outperforms the rest of techniques in terms of social welfare. The particle swarm optimizer is the only technique whose performance is close to ours, but its computation cost is much higher. Finally, we also study the effect of some graphs metrics on the gain that our approach can achieve.

PDF

SODA Conference 2009 Conference Paper

Decomposition of multiple coverings into more parts

Greg Aloupis
Jean Cardinal
Sébastien Collette
Stefan Langerman
David Orden
Pedro Ramos 0001

We prove that for every centrally symmetric convex polygon Q, there exists a constant α such that any αk -fold covering of the plane by translates of Q can be decomposed into k coverings. This improves on a quadratic upper bound proved by Pach and Tóth (SoCG'07). The question is motivated by a sensor network problem, in which a region has to be monitored by sensors with limited battery life.

Details