Options
John Augustine
Loading...
Preferred name
John Augustine
Official Name
John Augustine
Alternative Name
Augustine, John
Main Affiliation
Email
Scopus Author ID
Google Scholar ID
13 results
Now showing 1 - 10 of 13
- PublicationLocalized geometric query problems(01-04-2013)
; ;Das, Sandip ;Maheshwari, Anil ;Nandy, Sabhas C. ;Roy, SasankaSarvattomananda, SwamiA new class of geometric query problems are studied in this paper. We are required to preprocess a set of geometric objects P in the plane, so that for any arbitrary query point q, the largest circle that contains q but does not contain any member of P, can be reported efficiently. The geometric sets that we consider are point sets and boundaries of simple polygons. © 2012 Elsevier B.V. - PublicationLeader Election in Sparse Dynamic Networks with Churn(01-11-2016)
; ;Kulkarni, TejasSivasubramaniam, SumathiWe investigate the problem of electing a leader in a sparse but well-connected synchronous dynamic network in which up to a fraction of the nodes chosen adversarially can leave/join the network per time step. At this churn rate, all nodes in the network can be replaced by new nodes in a constant number of rounds. Moreover, the adversary can shield a fraction of the nodes (which may include the leader) by repeatedly churning their neighborhood and, thus, hindering, their communication with the rest of the network. However, empirical studies in peer-to-peer networks have shown that a significant fraction of the nodes are usually stable and well connected. It is, therefore, natural to take advantage of such stability to establish a leader that can maintain good communication with the rest of the nodes. Because the dynamics could change eventually, it is also essential to reelect a new leader whenever the current leader either has left the network or is not well-connected with rest of the nodes. In such reelections, care must be taken to avoid premature and spurious leader election resulting in more than one leader being present in the network at the same time. We assume a broadcast-based communication model in which each node can send up to O(log3n) bits per round and is unaware of its receivers a priori. We present a randomized algorithm that can, in O(log n) rounds, detect and reach consensus about the health of the leader (i.e., whether it is able to maintain good communication with rest of the network). In the event that the network decides that the leader’s ability to communicate is unhealthy, a new leader is reelected in a further O(log2n) rounds. Our running times hold with high probability provided a sufficiently large fraction of the nodes remain stable during the reelection process. Furthermore, we are guaranteed with high probability that there is at most one leader at any time. - PublicationMinimax regret 1-sink location problem in dynamic path networks(11-07-2015)
;Higashikawa, Yuya; ;Cheng, Siu Wing ;Golin, Mordecai J. ;Katoh, Naoki ;Ni, Guanqun ;Su, BingXu, YinfengThis paper considers the minimax regret 1-sink location problem in dynamic path networks. In our model, a dynamic path network consists of an undirected path with positive edge lengths and uniform edge capacity, and each vertex supply which is nonnegative value is unknown but only the interval of supply is known. A particular assignment of supply to each vertex is called a scenario. Under any scenario, the cost of a sink location is defined as the minimum time to complete the evacuation for all supplies (evacuees), and the regret of a sink location x is defined as the cost of x minus the cost of the optimal sink location. Then, the problem is to find a point as a sink such that the maximum regret for all possible scenarios is minimized. We propose an O(nlog n) time algorithm for the minimax regret 1-sink location problem in dynamic path networks with uniform capacity, where n is the number of vertices in the network. - PublicationRandomized gathering of asynchronous mobile robots(16-02-2021)
;Pattanayak, Debasish; Mandal, Partha SarathiThis paper revisits the widely researched gathering problem for two robots without any agreement on the coordinate system in a scenario which allows randomization in the asynchronous scheduling model. The scheduler is considered to be the adversary which determines the activation schedule of the robots. The adversary comes in three flavors, namely, adaptive offline, adaptive online, and oblivious, based on the knowledge of the outcome of random bits. The robots follow wait-look-compute-move cycle. In this paper, we classify the problems based on the capability of the adversary to control the parameters such as wait time, computation delay and the speed of robots and check the feasibility of gathering in terms of adversarial knowledge and capabilities. First, we show the impossibility of gathering under an adaptive offline adversary with non-negative wait time and non-negative computation delay. Gradually relaxing the adversarial capabilities, we present impossibility of gathering for finite random choices and improbability for infinite random choices for an adaptive online adversary. Under an oblivious adversary, we establish the possibility of gathering with zero computation delay. We improve the runtime of the algorithm by restricting the oblivious adversary to choose wait time and computation delay such that the sum of wait time and computation delay is more than a positive constant. Finally, we also extend our algorithm for multiple robots with merging. - PublicationBALANCED ALLOCATION: PATIENCE IS NOT A VIRTUE(01-01-2022)
; ;Moses, William K. ;Redlich, AmandaUpfal, EliLoad balancing is a well-studied problem, with balls-in-bins being the primary framework. The greedy algorithm Greedy[d] of Azar et al. [SIAM J. Comput., 29 (1999), pp. 180-200] places each ball by probing d > 1 random bins and placing the ball in the least loaded of them. With high probability, the maximum load under Greedy[d] is exponentially lower than the result when balls are placed uniformly randomly. Vöcking [J. ACM, 50 (2003), pp. 568-589] showed that a slightly asymmetric variant, Left[d], provides a further significant improvement. However, this improvement comes at the additional computational cost of imposing structure on the bins. Here, we present a fully decentralized and easy-to-implement algorithm called FirstDiff[d] that combines the simplicity of Greedy[d] and the improved balance of Left[d]. The key idea in FirstDiff[d] is to probe until a different bin size from the first observation is located and then place the ball. Although the number of probes could be quite large for some of the balls, we show that FirstDiff[d] requires only at most d probes on average per ball (in both the standard and the heavily loaded settings). Thus the number of probes is no greater than that of either Greedy[d] or Left[d]. More importantly, we show that FirstDiff[d] closely matches the improved maximum load ensured by Left[d] in both the standard and heavily loaded settings. We further provide a tight lower bound on the maximum load up to O(log log log n) terms. We additionally give experimental data that FirstDiff[d] is indeed as good as Left[d], if not better, in practice. - PublicationScheduling mechanisms to control the spread of COVID-19(01-09-2022)
; ;Hourani, Khalid ;Molla, Anisur Rahaman ;Pandurangan, GopalPasic, AdiWe study scheduling mechanisms that explore the trade-off between containing the spread of COVID-19 and performing in-person activity in organizations. Our mechanisms, referred to as group scheduling, are based on partitioning the population randomly into groups and scheduling each group on appropriate days with possible gaps (when no one is working and all are quarantined). Each group interacts with no other group and, importantly, any person who is symptomatic in a group is quarantined. We show that our mechanisms effectively trade-off in-person activity for more effective control of the COVID-19 virus spread. In particular, we show that a mechanism which partitions the population into two groups that alternatively work in-person for five days each, flatlines the number of COVID-19 cases quite effectively, while still maintaining in-person activity at 70% of pre-COVID-19 level. Other mechanisms that partitions into two groups with less continuous work days or more spacing or three groups achieve even more aggressive control of the virus at the cost of a somewhat lower in-person activity (about 50%). We demonstrate the efficacy of our mechanisms by theoretical analysis and extensive experimental simulations on various epidemiological models based on real-world data. - PublicationDistributed Graph Realizations(01-06-2022)
; ;Choudhary, Keerti ;Cohen, Avi ;Peleg, David ;Sivasubramaniam, SumathiSourav, SumanWe study graph realization problems for the first time from a distributed perspective. Graph realization problems are encountered in distributed construction of overlay networks that must satisfy certain degree or connectivity properties. We study them in the node capacitated clique (NCC) model of distributed computing, recently introduced for representing peer-to-peer overlay networks. We focus on two central variants, degree-sequence realization and minimum threshold-connectivity realization. In the degree sequence problem, each node $v$v is associated with a degree $d(v)$d(v), and the resulting degree sequence is realizable if it is possible to construct an overlay network in which the degree of each node $v$v is $d(v)$d(v). The minimum threshold-connectivity problem requires us to construct an overlay network that satisfies connectivity constraints specified between every pair of nodes. Overlay network realizations can be either explicit or implicit. Explicit realizations require both endpoints of any edge in the realized graph to be aware of the edge. In implicit realizations, on the other hand, at least one endpoint of each edge of the realized graph needs to be aware of the edge. The main realization algorithms we present are the following. (Note that all our algorithms are randomized Las Vegas algorithms unless specified otherwise. The stated running times hold with high probability.) 1) An $\tilde{O}(\min \lbrace \sqrt{m},\Delta \rbrace)$Õ(min{m,Δ}) time algorithm for implicit realization of a degree sequence. Here, $\Delta = \max _v d(v)$Δ=maxvd(v) is the maximum degree and $m = (1/2) \sum _v d(v)$m=(1/2)∑vd(v) is the number of edges in the final realization. 2) $\tilde{O}(\Delta)$Õ(Δ) time algorithm for an explicit realization of a degree sequence. We first compute an implicit realization and then transform it into an explicit one in $\tilde{O}(\Delta)$Õ(Δ) additional rounds. 3) An $\tilde{O}(\Delta)$Õ(Δ) time algorithm for the threshold connectivity problem that obtains an explicit solution and an improved $\tilde{O}(1)$Õ(1) algorithm for implicit realization when all nodes know each other's IDs. These algorithms yield 2-approximations w.r.t. the number of edges. We complement our upper bounds with lower bounds to show that the above algorithms are tight up to factors of $\log n$logn. Additionally, we provide algorithms for realizing trees (including a procedure for obtaining a tree with a minimal diameter), an $\tilde{O}(1)$Õ(1) round algorithm for approximate degree sequence realization and finally an $O(\log ^2 n)$O(log2n) algorithm for degree sequence realization in the non-preassigned case namely, where the input degree sequence may be permuted among the nodes. - PublicationMinmax Regret k-Sink Location on a Dynamic Path Network with Uniform Capacities(16-09-2019)
;Arumugam, Guru Prakash; ;Golin, Mordecai J.Srikanthan, PrashanthIn Dynamic flow networks an edge’s capacity is the amount of flow (items) that can enter it in unit time. All flow must be moved to sinks and congestion occurs if flow has to wait at a vertex for other flow to leave. In the uniform capacity variant all edges have the same capacity. The minmax k-sink location problem is to place k sinks minimizing the maximum time before all items initially on vertices can be evacuated to a sink. The minmax regret version introduces uncertainty into the input; the amount at each source is now only specified to within a range. The problem is to find a universal solution (placement of k sinks) whose regret (difference from optimal for a given input) is minimized over all inputs consistent with the given range restrictions. The previous best algorithms for the minmax regret version of the k-sink location problem on a path with uniform capacities ran in O(n) time for k= 1 , O(nlog 4n) time for k= 2 and Ω(nk+1) for k> 2. A major bottleneck to improving those solutions was that minmax regret seemed an inherently global property. This paper derives new combinatorial insights that allow decomposition into local problems. This permits designing two new algorithms. The first runs in O(n3log n) time independent of k and the second in O(nk2log k+1n) time. These improve all previous algorithms for k> 1 and, for k> 2 , are the first polynomial time algorithms known. - PublicationDynamics of profit-sharing games(01-01-2015)
; ;Chen, Ning ;Elkind, Edith ;Fanelli, Angelo ;Gravin, NickShiryaev, DmitryAn important task in the analysis of multiagent systems is to understand how groups of selfish players can form coalitions, i.e., work together in teams. In this paper, we study the dynamics of coalition formation under bounded rationality. We consider settings whereby each team’s profit is given by a submodular function and propose three profit-sharing schemes, each of which is based on the concept of marginal utility. The agents are assumed to be myopic, i.e.they keep changing teams as long as they can increase their payoff by doing so. We study the properties (such as closeness to Nash equilibrium or total profit) of the states that result after a polynomial number of such moves, and prove bounds on the price of anarchy and the price of stability of the corresponding games - PublicationDistributed agreement in dynamic peer-to-peer networks(01-11-2015)
; ;Pandurangan, Gopal ;Robinson, PeterUpfal, EliMotivated by the need for robust and fast distributed computation in highly dynamic Peer-to-Peer (P2P) networks, we present first-known, fully-distributed algorithms for the fundamental distributed agreement problem in dynamic networks that experience heavy node churn (i.e., nodes join and leave the network continuously over time). Our algorithms guarantee stable almost-everywhere agreement with high probability even under high adversarial churn and run in time that is polylogarithmic in n (which is the stable network size). Our first algorithm can tolerate a churn of up to εn per time step, sends only polylogarithmic number of bits per node per time step, and works under an adversary that is oblivious to the algorithm's random choices. Our second algorithm, designed for the more challenging adaptive adversary, can tolerate a churn of up to εn. Being easy to implement, our algorithms could serve as building blocks for other non-trivial distributed computation in dynamic networks.