Search
Results
-
Min-Cost Bipartite Perfect Matching with Delays
(2017)Leibniz International Proceedings in Informatics (LIPIcs) ~ Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)In the min-cost bipartite perfect matching with delays (MBPMD) problem, requests arrive online at points of a finite metric space. Each request is either positive or negative and has to be matched to a request of opposite polarity. As opposed to traditional online matching problems, the algorithm does not have to serve requests as they arrive, and may choose to match them later at a cost. Our objective is to minimize the sum of the distances ...Conference Paper -
Brief Announcement: Towards Reduced Instruction Sets for Synchronization
(2017)Leibniz International Proceedings in Informatics (LIPIcs) ~ 31st International Symposium on Distributed Computing (DISC 2017)Contrary to common belief, a recent work by Ellen, Gelashvili, Shavit, and Zhu has shown that computability does not require multicore architectures to support "strong" synchronization instructions like compare-and-swap, as opposed to combinations of "weaker" instructions like decrement and multiply. However, this is the status quo, and in turn, most efficient concurrent data-structures heavily rely on compare-and-swap (e.g. for swinging ...Conference Paper -
Distributed stable matching with similar preference lists
(2017)Leibniz International Proceedings in Informatics (LIPIcs) ~ 20th International Conference on Principles of Distributed Systems (OPODIS 2016)Consider a complete bipartite graph of 2n nodes with n nodes on each side. In a round, each node can either send at most one message to a neighbor or receive at most one message from a neighbor. Each node has a preference list that ranks all its neighbors in a strict order from 1 to n. We introduce a non-negative similarity parameter D < n for the preference lists of nodes on one side only. For D = 0, these preference lists are same and ...Conference Paper -
A Tight Lower Bound for the Capture Time of the Cops and Robbers Game
(2017)Leibniz International Proceedings in Informatics (LIPIcs) ~ 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)For the game of Cops and Robbers, it is known that in 1-cop-win graphs, the cop can capture the robber in O(n) time, and that there exist graphs in which this capture time is tight. When k >= 2, a simple counting argument shows that in k-cop-win graphs, the capture time is at most O(n^{k + 1}), however, no non-trivial lower bounds were previously known; indeed, in their 2011 book, Bonato and Nowakowski ask whether this upper bound can be ...Conference Paper