Author name cluster

Hoon Oh

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.

7 papers

2 author rows

SODA Conference 2022 Conference Paper

An Improved Local Search Algorithm for k-Median

Vincent Cohen-Addad
Anupam Gupta 0001
Lunjia Hu
Hoon Oh
David Saulpic

We present a new local-search algorithm for the k -median clustering problem. We show that local optima for this algorithm give a (2. 836 + ∊ )-approximation; our result improves upon the (3 + ∊ )-approximate local-search algorithm of Arya et al. [AGK + 01]. Moreover, a computer-aided analysis of a natural extension suggests that this approach may lead to an improvement over the best-known approximation guarantee for the problem. The new ingredient in our algorithm is the use of a potential function based on both the closest and second-closest facilities to each client. Specifically, the potential is the sum over all clients, of the distance of the client to its closest facility, plus (a small constant times) the truncated distance to its second-closest facility. We move from one solution to another only if the latter can be obtained by swapping a constant number of facilities, and has a smaller potential than the former. This refined potential allows us to avoid the bad local optima given by Arya et al. for the local-search algorithm based only on the cost of the solution.

Details

TCS Journal 2020 Journal Article

Radio aggregation scheduling

Rajiv Gandhi
Magnús M. Halldórsson
Christian Konrad
Guy Kortsarz
Hoon Oh

We consider the aggregation problem in radio networks: find a spanning tree in a given graph and a conflict-free schedule of the edges so as to minimize the latency of the computation. While a large body of literature exists on this and related problems, we give the first approximation results in graphs that are not induced by unit ranges in the plane. We give a polynomial-time O ˜ ( d n ) -approximation algorithm, where d is the average degree and n the number of vertices in the graph, and show that the problem is Ω ( n 1 − ϵ ) -hard (and Ω ( ( d n ) 1 / 2 − ϵ ) -hard) to approximate even on bipartite graphs, for any ϵ > 0, rendering our algorithm essentially optimal. We also obtain a O ( log ⁡ n ) -approximation in interval graphs.

Details DOI

AAAI Conference 2020 Conference Paper

To Signal or Not To Signal: Exploiting Uncertain Real-Time Information in Signaling Games for Security and Sustainability

Elizabeth Bondi
Hoon Oh
Haifeng Xu
Fei Fang
Bistra Dilkina
Milind Tambe

Motivated by real-world deployment of drones for conservation, this paper advances the state-of-the-art in security games with signaling. The well-known defender-attacker security games framework can help in planning for such strategic deployments of sensors and human patrollers, and warning signals to ward off adversaries. However, we show that defenders can suffer signiﬁcant losses when ignoring real-world uncertainties despite carefully planned security game strategies with signaling. In fact, defenders may perform worse than forgoing drones completely in this case. We address this shortcoming by proposing a novel game model that integrates signaling and sensor uncertainty; perhaps surprisingly, we show that defenders can still perform well via a signaling strategy that exploits uncertain real-time information. For example, even in the presence of uncertainty, the defender still has an informational advantage in knowing that she has or has not actually detected the attacker; and she can design a signaling scheme to “mislead” the attacker who is uncertain as to whether he has been detected. We provide theoretical results, a novel algorithm, scale-up techniques, and experimental results from simulation based on our ongoing deployment of a conservation drone system in South Africa.

PDF Details

AAMAS Conference 2019 Conference Paper

Broken Signals in Security Games: Coordinating Patrollers and Sensors in the Real World

Elizabeth Bondi
Hoon Oh
Haifeng Xu
Fei Fang
Bistra Dilkina
Milind Tambe

Mobile sensors, e. g. , unmanned aerial vehicles (UAVs), are becoming increasingly important in security domains and can be used for tasks such as searching for poachers in conservation areas. Such mobile sensors augment human patrollers by assisting in surveillance and in signaling potentially deceptive information to adversaries, and their coordinated deployment could be modeled via the well-known security games framework. Unfortunately, real-world uncertainty in the sensor’s detection of adversaries and adversaries’ observation of the sensor’s signals present major challenges in the sensors’ use. This leads to significant detriments in security performance. We first discuss the current shortcomings in more detail, and then propose a novel game model that incorporates uncertainty with sensors. The defender strategy in this game model will consist of three interdependent stages: an allocation stage, a signaling stage, and a reaction stage.

PDF

AAAI Conference 2019 Conference Paper

Fairly Allocating Many Goods with Few Queries

Hoon Oh
Ariel D. Procaccia
Warut Suksompong

We investigate the query complexity of the fair allocation of indivisible goods. For two agents with arbitrary monotonic valuations, we design an algorithm that computes an allocation satisfying envy-freeness up to one good (EF1), a relaxation of envy-freeness, using a logarithmic number of queries. We show that the logarithmic query complexity bound also holds for three agents with additive valuations. These results suggest that it is possible to fairly allocate goods in practice even when the number of goods is extremely large. By contrast, we prove that computing an allocation satisfying envyfreeness and another of its relaxations, envy-freeness up to any good (EFX), requires a linear number of queries even when there are only two agents with identical additive valuations.

PDF Details

AAMAS Conference 2019 Conference Paper

Optimal Trip-Vehicle Dispatch with Multi-Type Requests

Taoan Huang
Bohui Fang
Hoon Oh
Xiaohui Bei
Fei Fang

In recent years, traditional transportation platforms which mainly provide real-time ride-hailing services have started to accept rides scheduled in advance. The presence of both ride requests posted in real time and scheduled rides leads to new challenges to the service providers in deciding which requests to accept and how to dispatch the vehicles in a dynamic and optimal way, which, to the best of our knowledge, have not been addressed by existing works. To fill the gap, we provide the following contributions: (i) a novel two-stage decision-making model where in the first stage, the system decides whether to accept requests scheduled in advance in an online fashion, and in the second stage, dispatches vehicles to on-demand ride requests in real time given the accepted scheduled requests as constraints; (ii) novel algorithms for both stages that take an estimated distribution of on-demand ride requests into account to handle both on-demand and scheduled requests.

PDF

AAMAS Conference 2019 Conference Paper

Using Game Theory in Real Time in the Real World: A Conservation Case Study

Elizabeth Bondi
Hoon Oh
Haifeng Xu
Fei Fang
Bistra Dilkina
Milind Tambe

In the real world, real-time data are now widely available, especially in security domains. Security cameras, aerial imagery, and even social media keep defenders informed when protecting important events, locations, and people. Further, advances in artificial intelligence have led to tools that can interpret these data automatically. Game theoretic models, for example, have shown great success in security. However, most of them ignore real-time information. In this paper, we demonstrate the potential to use real-time information from imagery to better inform our decisions in game theoretic models for security. As a concrete example, a conservation group called Air Shepherd uses conservation drones equipped with thermal infrared cameras to locate poachers at night and alert park rangers. They have also used lights aboard the drones, or signaled, to warn poachers of their presence, which often deters the poachers. We propose a system that (i) allocates drones and humans strategically throughout a protected area, (ii) detects poachers in the thermal infrared videos recorded by the conservation drones flying through the protected area in the predetermined location, and (iii) recommends moving to the location and/or signaling to the poacher that a patroller is nearby depending on real-time detections. View the demonstration: http: //bit. ly/aamas19-demo-bondi-et-al.

PDF