Search Results (1 - 4 of 4 Results)

Sort By  
Sort Dir
 
Results per page  

Rossi, Alfred VincentTemporal Clustering of Finite Metric Spaces and Spectral k-Clustering
Doctor of Philosophy, The Ohio State University, 2017, Computer Science and Engineering
This thesis addresses clustering problems in two distinct settings. In the first setting we explore the notion of what it means for a graph to admit a good partition into k-clusters. We say a partition of a graph is strong if each cluster has small external conductance, and large internal conductance. We consider a natural embedding of the graph into Rk involving the first k eigenvectors of the graph's Laplacian matrix. We show that for graphs which admit a sufficiently strong k-partition, much of the l2-mass of each partition element concentrates around a distinct point in the embedding. Further, we show how to estimate the degree of concentration as well as the separation of the k embedding points from the input graph. We exploit this fact to design a simple greedy spectral clustering algorithm, spectral k-clustering, which returns a partition that is provably close to a strong partition, provided that the input graph admits one. A recent result shows that strong partitions exist for graphs with a sufficiently large spectral gap between the k-th and (k+1)-st eigenvalues. Taking this together with our main theorem gives a spectral algorithm which finds a good partition in graphs with a sufficiently large spectral gap. Finally, we provide an experimental evaluation of the algorithm on inputs which do not necessarily satisfy the conditions required by our theorems. The second setting concerns metric spaces which change over time. Here, our goal is to find a temporally coherent clustering. We introduce a framework for clustering finite sequences of metric spaces taken from a common ambient metric space and study generalizations of some classic clustering problems to this setting. Formally, let P denote this sequence of metric subspaces, which we call a temporal-sampling. Given a collection of clusters, C, we quantify the quality of the clustering under multiple objectives: complexity (size, |.|), a spatial clustering cost (μ), and a temporal cost (δ) which is small when the clusters exhibit good locality. For a fixed choice of objectives, we say that a temporal-sampling admits a temporal (k, r, δ)-clustering for some k in N, r in R≥0, δ in R≥0 if there exists a clustering C of P such that |C| <= k, μ(C) <= r, and δ(C) <= δ. For certain choices of objectives, we study the problem of deciding in polynomial-time whether or not a temporal-sampling admits a temporal (k, r, δ)-clustering when k, r, and δ are taken to be some functions of the input. Further, let α, β, γ be positive real numbers which are all at least 1. An algorithm is a temporal (α, β, γ)-approximation if it is guaranteed to return a temporal (α k, β r, γ δ)-clustering whenever P admits a temporal (k, r, δ)-clustering. We study the existence of polynomial-time temporal (α, β, γ)-approximations under various assumptions. We give several approximation algorithms of this kind and exhibit some conditions under which approximation is NP-hard. Last, we introduce a model for hierarchical temporal clusterings and give a polynomial-time approximation algorithm.

Committee:

Tamal K. Dey (Advisor); Anastasios Sidiropoulos (Advisor); Yusu Wang (Committee Member); Brian Winer (Committee Member)

Subjects:

Computer Science

Keywords:

clustering; multi-objective optimization; dynamic metric spaces; approximation algorithms; hardness of approximation

Hu, XiaohongProbability modeling of industrial situations using transform techniques
Master of Science (MS), Ohio University, 1995, Industrial and Manufacturing Systems Engineering (Engineering)
This thesis removed at the request of Ohio University (6/2013)

Committee:

Helmut Zwahlen (Advisor)

Subjects:

Engineering, Industrial

Keywords:

Probability Modeling Techniques; Transform and Monte Carlo Simulation Methods; Polygon Approximation Algorithms

Zheng, ZizhanSparse Deployment of Large Scale Wireless Networks for Mobile Targets
Doctor of Philosophy, The Ohio State University, 2010, Computer Science and Engineering

Deploying wireless networks at large scale is challenging. Despite various effort made in the design of coverage schemes and deployment algorithms with static targets in mind, how to deploy a wireless network to achieve a desired quality of service for mobile targets moving in a large region without incurring prohibitive cost largely remains open. To address this issue, this dissertation proposes Sparse Coverage, a deployment scheme that provides guaranteed service to mobile targets while trading off service quality with cost in a deterministic way.

The first part of this dissertation discusses two sparse coverage models for deploying WiFi access points (APs) along a city-wide road network to provide data service to mobile vehicles. The first model, called Alpha Coverage, ensures that a vehicle moving through a path of length α is guaranteed to have a contact with some AP. This is the first partial coverage model (in contrast to the more expensive full coverage model) that provides a performance guarantee to disconnection-tolerant mobile users. We show that under this general definition, even to verify whether a given deployment provides Alpha Coverage is co-NPC. Thus, we propose two practical metrics as approximations, and design efficient approximation algorithms for each of them. The concept of Alpha Coverage is then extended by taking connectivity into account. To characterize the performance of a roadside WiFi network more accurately, we propose the second sparse coverage model, called Contact Opportunity, which measures the fraction of distance or time that a mobile user is in contact with some AP. We present an efficient deployment method that maximizes the worst-case contact opportunity under a budget constraint by exploiting submodular optimization techniques. We further extend this notion to the more intuitive metric -- average throughput -- by taking various uncertainties involved in the system into account.

The second part of this dissertation studies sparse deployment techniques for placing sensor nodes in a large 2-d region for tracking movements. We propose a sparse coverage model called Trap Coverage, which provides a bound on the largest gap that a mobile target, e.g., an intruder or a dynamic event, is missed by any sensor node. In contrast to the current probabilistic partial coverage models, this is the first 2-d coverage model that can trade off the quality of tracking with network lifetime in a deterministic way. For an arbitrarily deployed sensor network, we propose efficient algorithms for determining the level of Trap Coverage even if the sensing regions have non-convex or uncertain boundaries. We then discuss a roadmap assisted geographic routing protocol to support efficient pairwise routing in large sensor networks with holes, which embodies a novel hole approximation technique and makes desired tradeoff between route-stretch and control overhead.

Committee:

Prasun Sinha (Advisor); Ness Shroff (Committee Member); Yusu Wang (Committee Member)

Subjects:

Computer Science

Keywords:

Wireless networks; sensor networks; coverage; sparse coverage; approximation algorithms

Jones, Jeffrey S.Analysis of Algorithms for Star Bicoloring and Related Problems
Doctor of Philosophy (PhD), Ohio University, 2015, Computer Science (Engineering and Technology)
This dissertation considers certain graph-theoretic combinatorial problems which have direct application to the efficient computation of derivative matrices (“Jacobians”) which arise in many scientific computing applications. Specifically, we analyze algorithms for Star Bicoloring and establish several analytical results. We establish complexity-theoretic lower bounds on the approximability of algorithms for Star Bicoloring, showing that no such polynomial-time algorithm can achieve an approximation ratio of O(N ^(1/3)-e ) for any e > 0 unless P = NP. We establish the first algorithm (ASBC) for Star Bicoloring with a known approximation upper-bound, showing that ASBC is an O(N ^(2/3 )) polynomial-time approximation algorithm. Based on extension of these results we design a generic framework for greedy Star Bicoloring, and implement several specific methods for comparison. General analysis techniques are developed and applied to both algorithms from the literature (CDC, Hossain and Steihaug, 1998 [1]) as well as those developed as part of the framework. We provide numerous approximability results including the first approximation analysis for the CDC algorithm, showing that CDC is an O(N ^(3/4) ) approximation algorithm. Finally, we observe that all algorithms within this generic framework produce a restricted class of star bicolorings that we refer to as Distance-2 Independent Set Colorings (D2ISC). We establish the relationship between Star Bicoloring and D2ISC. In particular we show that these two notions are not equivalent, that D2ISC is NP-complete and that it cannot be approximated to within O(N ^(1/3 -e) ) for any e > 0 unless P = NP.

Committee:

David Juedes, Ph.D. (Advisor); Razvan Bunescu, Ph.D. (Committee Member); Frank Drews, Ph.D. (Committee Member); Cynthia Marling, Ph.D. (Committee Member); Sergio Lopez, Ph.D. (Committee Member); Howard Dewald, Ph.D. (Committee Member)

Subjects:

Applied Mathematics; Computer Science

Keywords:

star bicoloring; acyclic bicoloring; Jacobian matrix computation; approximation algorithms; greedy star bicoloring; Jacobian matrix optimization; greedy optimization methods