About

Michael Dillencourt is a professor in the Department of Computer Science at UC Irvine's Donald Bren School of Information & Computer Sciences. His research interests include computational geometry, graph theory, and distributed computing. Within computational geometry, he has investigated the structure of Delaunay triangulations and the family of inscribable polyhedra. Additionally, he has developed efficient algorithms for component-labeling and boundary extraction in binary images, which are applicable to various image-representation schemes. Dr. Dillencourt earned his Ph.D. from the University of Maryland in 1988.

Research topics

• Computer Science
• Algorithm
• Discrete mathematics
• Mathematics
• Combinatorics

Selected publications

• Leveraging parameterized Chernoff bounds for simplified algorithm analyses

  Information Processing Letters · 2024

  1st authorCorresponding
  • Computer Science
  • Computer Science
  • Algorithm

  In this paper, we derive parameterized Chernoff bounds and show their applications for simplifying the analysis of some well-known probabilistic algorithms and data structures. The parameterized Chernoff bounds we provide give probability bounds that are powers of two, with a clean formulation of the relation between the constant in the exponent and the relative distance from the mean. In addition, we provide new simplified analyses with these bounds for hash tables, randomized routing, and a simplified, non-recursive adaptation of the Floyd-Rivest selection algorithm.

  PublisherDOI

• Simplified Chernoff bounds with powers-of-two probabilities

  Information Processing Letters · 2023 · 3 citations

  1st authorCorresponding
  • Computer Science
  • Algorithm
  • Computer Science

  In this paper, we derive simplified Chernoff bounds with powers-of-two probabilities, and we show their uses in analyzing probabilistic algorithms.

  PublisherDOI

• Yield Optimization with Binding Latency Constraints

  2016-11-01 · 3 citations

  article

  Programmatic advertising is an actively developing industry and research area. Some of the research in this area concerns the development of optimal or approximately optimal contracts and policies between publishers, advertisers and intermediaries such as ad networks and ad exchanges. Both the development of contracts and the construction of policies governing their implementation are difficult challenges, and different models take different features of the problem into account. In programmatic advertising decisions are made in real time, and time is a scarce resource particularly for publishers who are concerned with content load times. Policies for advertisement placement must execute very quickly once content is requested, this requires policies to either be pre-computed and accessed as needed, or for the policy execution to be very efficient. In this paper we formulate a stochastic optimization problem for per publisher ad sequencing with binding latency constraints. We adopt a well known heuristic optimization technique to this problem and evaluate it's performance on real data instances. Our experimental results indicate that our heuristic algorithm is near optimal for instances where an optimality calculation is feasible, and superior to other reasonable approaches for instances when the calculation is not feasible.

  PublisherDOI

• Capturing Lombardi Flow in Orthogonal Drawings by Minimizing the Number of Segments

  arXiv (Cornell University) · 2016-08-13 · 1 citations

  preprintOpen access

  Inspired by the artwork of Mark Lombardi, we study the problem of constructing orthogonal drawings where a small number of horizontal and vertical line segments covers all vertices. We study two problems on orthogonal drawings of planar graphs, one that minimizes the total number of line segments and another that minimizes the number of line segments that cover all the vertices. We show that the first problem can be solved by a non-trivial modification of the flow-network orthogonal bend-minimization algorithm of Tamassia, resulting in a polynomial-time algorithm. We show that the second problem is NP-hard even for planar graphs with maximum degree 3. Given this result, we then address this second optimization problem for trees and series-parallel graphs with maximum degree 3. For both graph classes, we give polynomial-time algorithms for upward orthogonal drawings with the minimum number of segments covering the vertices.

  PublisherOA PDFDOI

• Distributed flow optimization control for energy-harvesting wireless sensor networks

  2014-06-01 · 5 citations

  article

  This paper proposes a distributed flow-based routing technique in energy-harvesting wireless sensor networks (EHWSNs) in order to balance the energy consumptions by sending packets assigned to routers that are sent from sensors to base stations. The objective of the flow optimization problem is to minimize the total load factors of all the nodes and wireless links, which leads to sustainable management of the sensor networks that exploit renewable power from energy harvesting systems. We propose a novel algorithm based on tie-set graph theory where the underlying graph of an EHWSN is divided into a set of independent loops to significantly reduce the topological complexity, which simplifies the flow optimization problem to be solved in a distributed manner. Simulation experiments against the shortest-path and multi-path algorithms demonstrate that optimized packet flows by the proposed method realize the sustainable EHWSNs and maintain the useful life of storage devices with modest increase in total energy consumption by routings.

  PublisherDOI

• Distributed power flow loss minimization control for future grid

  International Journal of Circuit Theory and Applications · 2014-05-09 · 10 citations

  articleOpen access

  Summary In this paper, a novel decentralized algorithm is proposed to minimize power flow loss in a large‐scale future grid connecting with many real‐time‐distributed generation systems by which power flows bi‐directionally. The DC‐power loss at each link is defined as the product of resistance and the square of current that can be considered as a quadratic flow cost. We employ the notion of tie‐sets that reduces the complexity of the power flow loss problem by dividing a power network into a set of loops that forms a linear vector space on which the power loss problem can be formulated as a convex optimization problem. As finding a solution in each tie‐set enables global optimization, we realize parallel computing within a system of independent tie‐sets by integrating autonomous agents. Simulation results demonstrate the minimization of the power loss on every link by iteratively optimized power flows and show the superiority against the traditional centralized optimization scheme. Copyright © 2014 John Wiley & Sons, Ltd.

  PublisherOA PDFDOI

• Improving numerical accuracy for non-negative matrix multiplication on GPUs using recursive algorithms

  2013-05-28 · 4 citations

  article

  Scientific computing is only bound by the limits of Moore's Law and the scalability of high performance mathematical library implementations. Most mathematical libraries however tend to focus only on general inputs, limiting their potential performance and scalability by not tailoring their implementation to specific inputs, such as non-negative inputs. By removing this limitation it is possible to improve the performance and accuracy of a range of problems. In this paper we explore the limitations of hardware to improve accuracy of non-negative matrix multiply by specifically comparing implementations on the GPU and CPU and propose algorithmic solutions to improve accuracy. Next, we demonstrate a matrix multiply implementation that takes advantage of asymptotically fast matrix multiply algorithms, which have been shown to scale better than O(N3) matrix multiply implementations, and improve accuracy by up to a whole digit while increasing performance by up to 27% for matrices where the input is positive. Finally, we propose to extend the BLAS level 3 specification to non-negative matrices to allow easy integration of our solution and allow other library authors to implement their own solutions as part of an existing standard.

  PublisherDOI

• Methods for mitigating and eliminating error in hybrid matrix multiply algorithms

  2013-01-01

  article1st authorCorresponding

  High performance dense matrix multiply implementations have largely reached their limit in terms of performance as efficiencies are very near 100%. In order to further increase performance, matrix multiply algorithms that are asymptotically faster than O(n3) must be used to reduce the overall amount of computation required. Asymptotically fast matrix multiply algorithms however have adverse affects on accuracy, and until recently, this accuracy problem was believed to be uncorrectable. Because of this, the adoption of hybrid dense matrix multiply algorithms (algorithms that combine asymptotically fast matrix multiply algorithms with high performance matrix multiply implementations), particularly by linear algebra library authors, has been non-existent. In this dissertation we present several solutions that in addition to mitigating or eliminating the error added by the asymptotically fast matrix multiply algorithm, (demonstrating that it is possible to use hybrid matrix multiply algorithms without adversely affecting accuracy), can also be used by themselves to improve the accuracy of standard matrix multiply implementations, when additional accuracy is required.

  Publisher

• Distributed Real-Time Power Flow control with renewable integration

  2013-10-01 · 8 citations

  articleOpen access

  We formulate an Optimal Real-Time Power Flow (ORPF) problem that integrates renwable energy generation and energy storage. In the ORPF problem, we seek to minimize the costs of energy storage and of power generation from fossil fuel that are required to balance the loads and generation from renewable sources. We present a novel decentralized algorithm for this problem, using tie-set graph theory. Tie-set graph theory significantly reduces the complexity of the ORPF problem by dividing a power network into a set of independent loops referred to as “tie-sets.” Simulation results demonstrate real-time power production responses and flow controls that lead to reliable use of battery systems and reduce the cost of using fossil fuel.

  PublisherOA PDFDOI

• Tie-set Based Fault Tolerance for autonomous recovery of double-link failures

  2013-07-01 · 3 citations

  article

  In this paper, we propose a mechanism for coping with double-link failures in an autonomous and distributed manner. We call it Tie-set Based Fault Tolerance (TBFT) because it utilizes tie-sets, which represent a set of the edges comprising a loop within the graph that represents the network. An autonomous distributed control method based on dividing a network into a set of tie-sets, whose union covers every edge in the network, has been verified to be more effective than traditional tree-based restoration techniques in case of single link failure. The proposed method efficiently and gracefully handle double-link failures and also decrease the communication overhead incurred during network configuration. We demonstrate these results by simulating and comparing TBFT with the traditional approach of using Rapid Spanning Tree Protocol (RSTP).

  PublisherDOI

Frequent coauthors

• Lubomir Bic

  University of California, Irvine

  53 shared

• Lei Pan

  14 shared

• Ming Kin Lai

  University of California, Irvine

  11 shared

• Munehiro Fukuda

  University of Washington Bothell

  9 shared

• Hairong Kuang

  Meta (United States)

  7 shared

• David Eppstein

  7 shared

• Fehmina Merchant

  University of California, Irvine

  6 shared

• Michael T. Goodrich

  University of California, Irvine

  5 shared