Search

Dimensional synthesis refers to design of the dimensions of manipulators by optimising different kinds of performance indices. The motivation of this study is to perform dimensional synthesis for a wide set of spatial manipulators by optimising the manipulability of each manipulator around a pre-defined task point in the workspace and to finally give a prescription of manipulators along with their dimensions optimised for velocity and force transmission. A systematic method to formulate Jacobian matrix of a manipulator is presented. Optimisation of manipulability is performed for manipulation of the end-effector around a chosen task point for 96 1-DOF manipulators, 645 2-DOF manipulators, 8 3-DOF manipulators and 15 4-DOF manipulators taken from the result of enumeration of manipulators that is done in its companion paper devoted to enumeration of possible manipulators up to a number of links. Prescriptions for these sets of manipulators are presented along with their scaled condition numbers and their ordered indices. This gives the designer a prescription of manipulators with their optimised dimensions that reflects the performance of the end-effector around the given task point for velocity and force transmission.

This study is on the enumeration of spatial robotic manipulators, which is an essential basis for a companion study on dimensional synthesis, both of which together present a wider utility in manipulator synthesis. The enumeration of manipulators is done by using adjacency matrix concept. In this paper, a novel way of applying adjacency matrix to spatial manipulators with four types of joints, namely revolute, prismatic, cylindrical and spherical joints, is presented. The limitations of the applicability of the concept to 3D manipulators are discussed. 1-DOF (Degree Of Freedom) manipulators of four links and 2-DOF, 3-DOF and 4-DOF manipulators of three links, four links and five links, are enumerated based on a set of conventions and some assumptions. Finally, 96 1-DOF manipulators of four links, 641 2-DOF manipulators of 5 links, 4 2-DOF manipulators of three links, 8 3-DOF manipulators of four links and 15 4-DOF manipulators of five links are presented.

Characterizing shapes of high-dimensional objects via Ricci curvatures plays a critical role in many research areas in mathematics and physics. However, even though several discretizations of Ricci curvatures for discrete combinatorial objects such as networks have been proposed and studied by mathematicians, the computational complexity aspects of these discretizations have escaped the attention of theoretical computer scientists to a large extent. In this paper, we study one such discretization, namely the Ollivier-Ricci curvature, from the perspective of efficient computation by fine-grained reductions and local query-based algorithms. Our main contributions are the following. (a) We relate our curvature computation problem to minimum weight perfect matching problem on complete bipartite graphs via fine-grained reduction. (b) We formalize the computational aspects of the curvature computation problems in suitable frameworks so that they can be studied by researchers in local algorithms. (c) We provide the first known lower and upper bounds on queries for query-based algorithms for the curvature computation problems in our local algorithms framework. En route, we also illustrate a localized version of our fine-grained reduction. We believe that our results bring forth an intriguing set of research questions, motivated both in theory and practice, regarding designing efficient algorithms for curvatures of objects., Comment: To appear in the journal "Theoretical Computer Science"

Ensuring fairness in computational problems has emerged as a $key$ topic during recent years, buoyed by considerations for equitable resource distributions and social justice. It $is$ possible to incorporate fairness in computational problems from several perspectives, such as using optimization, game-theoretic or machine learning frameworks. In this paper we address the problem of incorporation of fairness from a $combinatorial$ $optimization$ perspective. We formulate a combinatorial optimization framework, suitable for analysis by researchers in approximation algorithms and related areas, that incorporates fairness in maximum coverage problems as an interplay between $two$ conflicting objectives. Fairness is imposed in coverage by using coloring constraints that $minimizes$ the discrepancies between number of elements of different colors covered by selected sets; this is in contrast to the usual discrepancy minimization problems studied extensively in the literature where (usually two) colors are $not$ given $a$ $priori$ but need to be selected to minimize the maximum color discrepancy of $each$ individual set. Our main results are a set of randomized and deterministic approximation algorithms that attempts to $simultaneously$ approximate both fairness and coverage in this framework., Comment: Revised version, under submission to journal

The topic of this paper is "gerrymandering", namely the curse of deliberate creations of district maps with highly asymmetric electoral outcomes to disenfranchise voters, and it has a long legal history. Measuring and eliminating gerrymandering has enormous implications to sustain the backbone of democratic principles of a society. Although there is no dearth of legal briefs involving gerrymandering over many years, it is only more recently that mathematicians and applied computational researchers have started to investigate this topic. However, it has received relatively little attention so far from the computational complexity researchers dealing with theoretical analysis of computational complexity issues, such as computational hardness, approximability issues, etc. There could be many reasons for this, such as descriptions of these problem non-CS non-math (often legal or political) journals that theoretical CS (TCS) people usually do not follow, or the lack of coverage of these topics in TCS publication venues. One of our modest goals in writing this article is to improve upon this situation by stimulating further interactions between the gerrymandering and TCS researchers. To this effect, our main contributions are twofold: (1) we provide formalization of several models, related concepts, and corresponding problem statements using TCS frameworks from the descriptions of these problems as available in existing non-TCS (perhaps legal) venues, and (2) we also provide computational complexity analysis of some versions of these problems, leaving other versions for future research. The goal of writing this article is not to have the final word on gerrymandering, but to introduce a series of concepts, models and problems to the TCS community and to show that science of gerrymandering involves an intriguing set of partitioning problems involving geometric and combinatorial optimization., Comment: Disclaimer: The authors were not supported, financially or otherwise, by any political party. The research results reported in this paper are purely scientific and reported as they are without any regard to which political party they may be of help (if at all)

Widespread usage of complex interconnected social networks such as Facebook, Twitter and LinkedIn in modern internet era has also unfortunately opened the door for privacy violation of users of such networks by malicious entities. In this article we investigate, both theoretically and empirically, privacy violation measures of large networks under active attacks that was recently introduced in (Information Sciences, 328, 403-417, 2016). Our theoretical result indicates that the network manager responsible for prevention of privacy violation must be very careful in designing the network if its topology does not contain a cycle. Our empirical results shed light on privacy violation properties of eight real social networks as well as a large number of synthetic networks generated by both the classical Erdos-Renyi model and the scale-free random networks generated by the Barabasi-Albert preferential-attachment model., Comment: To appear in Information Sciences

$Anomaly$ $detection$ problems (also called $change$-$point$ $detection$ problems) have been studied in data mining, statistics and computer science over the last several decades in applications such as medical condition monitoring and weather change detection. In recent days, however, anomaly detection problems have become increasing more relevant in the context of $network$ $science$ since useful insights for many complex systems in biology, finance and social science are often obtained by representing them via networks. Notions of local and non-local curvatures of higher-dimensional geometric shapes and topological spaces play a $fundamental$ role in physics and mathematics in characterizing anomalous behaviours of these higher dimensional entities. However, using curvature measures to detect anomalies in networks is not yet very common. To this end, a main goal in this paper to formulate and analyze curvature analysis methods to provide the foundations of systematic approaches to find $critical$ $components$ and $detect$ $anomalies$ in networks. For this purpose, we use two measures of network curvatures which depend on non-trivial global properties, such as distributions of geodesics and higher-order correlations among nodes, of the given network. Based on these measures, we precisely formulate several computational problems related to anomaly detection in static or dynamic networks, and provide non-trivial computational complexity results for these problems. This paper must $not$ be viewed as delivering the final word on appropriateness and suitability of specific curvature measures. Instead, it is our hope that this paper will stimulate and motivate further theoretical or empirical research concerning the exciting interplay between notions of curvatures from network and non-network domains, a $much$ desired goal in our opinion., Comment: Final revised version; to appear in Algorithmica

Partisan gerrymandering is a major cause for voter disenfranchisement in United States. However, convincing US courts to adopt specific measures to quantify gerrymandering has been of limited success to date. Recently, Stephanopoulos and McGhee introduced a new and precise measure of partisan gerrymandering via the so-called "efficiency gap" that computes the absolutes difference of wasted votes between two political parties in a two-party system. Quite importantly from a legal point of view, this measure was found legally convincing enough in a US appeals court in a case that claims that the legislative map of the state of Wisconsin was gerrymandered; the case is now pending in US Supreme Court. In this article, we show the following: (a) We provide interesting mathematical and computational complexity properties of the problem of minimizing the efficiency gap measure. To the best of our knowledge, these are the first non-trivial theoretical and algorithmic analyses of this measure of gerrymandering. (b) We provide a simple and fast algorithm that can "un-gerrymander" the district maps for the states of Texas, Virginia, Wisconsin and Pennsylvania by bring their efficiency gaps to acceptable levels from the current unacceptable levels. Our work thus shows that, notwithstanding the general worst case approximation hardness of the efficiency gap measure as shown by us,finding district maps with acceptable levels of efficiency gaps is a computationally tractable problem from a practical point of view. Based on these empirical results, we also provide some interesting insights into three practical issues related the efficiency gap measure. We believe that, should the US Supreme Court uphold the decision of lower courts, our research work and software will provide a crucial supporting hand to remove partisan gerrymandering.

With the arrival of modern internet era, large public networks of various types have come to existence to benefit the society as a whole and several research areas such as sociology, economics and geography in particular. However, the societal and research benefits of these networks have also given rise to potentially significant privacy issues in the sense that malicious entities may violate the privacy of the users of such a network by analyzing the network and deliberately using such privacy violations for deleterious purposes. Such considerations have given rise to a new active research area that deals with the quantification of privacy of users in large networks and the corresponding investigation of computational complexity issues of computing such quantified privacy measures. In this paper, we formalize three such privacy measures for large networks and provide non-trivial theoretical computational complexity results for computing these measures. Our results show the first two measures can be computed efficiently, whereas the third measure is provably hard to compute within a logarithmic approximation factor. Furthermore, we also provide computational complexity results for the case when the privacy requirement of the network is severely restricted, including an efficient logarithmic approximation., Comment: 21 pages, 3 figures

In phylogenetics, phylogenetic trees are rooted binary trees, whereas phylogenetic networks are rooted arbitrary acyclic digraphs. Edges are directed away from the root and leaves are uniquely labeled with taxa in phylogenetic networks. For the purpose of validating evolutionary models, biologists check whether or not a phylogenetic tree is contained in a phylogenetic network on the same taxa. This tree containment problem is known to be NP-complete. A phylogenetic network is reticulation-visible if every reticulation node separates the root of the network from some leaves. We answer an open problem by proving that the problem is solvable in quadratic time for reticulation-visible networks. The key tool used in our answer is a powerful decomposition theorem. It also allows us to design a linear-time algorithm for the cluster containment problem for networks of this type and to prove that every galled network with n leaves has 2(n-1) reticulation nodes at most., Comment: The journal version of arXiv:1507.02119v2

$\delta$-hyperbolic graphs, originally conceived by Gromov in 1987, occur often in many network applications; for fixed $\delta$, such graphs are simply called hyperbolic graphs and include non-trivial interesting classes of "non-expander" graphs. The main motivation of this paper is to investigate the effect of the hyperbolicity measure $\delta$ on expansion and cut-size bounds on graphs (here $\delta$ need not be a constant), and the asymptotic ranges of $\delta$ for which these results may provide improved approximation algorithms for related combinatorial problems. To this effect, we provide constructive bounds on node expansions for $\delta$-hyperbolic graphs as a function of $\delta$, and show that many witnesses (subsets of nodes) for such expansions can be computed efficiently even if the witnesses are required to be nested or sufficiently distinct from each other. To the best of our knowledge, these are the first such constructive bounds proven. We also show how to find a large family of s-t cuts with relatively small number of cut-edges when s and t are sufficiently far apart. We then provide algorithmic consequences of these bounds and their related proof techniques for two problems for $\delta$-hyperbolic graphs (where $\delta$ is a function $f$ of the number of nodes, the exact nature of growth of $f$ being dependent on the particular problem considered)., Comment: Final corrected author version, to appear in the journal Algorithmica

In this work, we answer an open problem in the study of phylogenetic networks. Phylogenetic trees are rooted binary trees in which all edges are directed away from the root, whereas phylogenetic networks are rooted acyclic digraphs. For the purpose of evolutionary model validation, biologists often want to know whether or not a phylogenetic tree is contained in a phylogenetic network. The tree containment problem is NP-complete even for very restricted classes of networks such as tree-sibling phylogenetic networks. We prove that this problem is solvable in cubic time for stable phylogenetic networks. A linear time algorithm is also presented for the cluster containment problem., Comment: 25 pages, 3 figures

The strong metric dimension of a graph was first introduced by Seb\"{o} and Tannier (Mathematics of Operations Research, 29(2), 383-393, 2004) as an alternative to the (weak) metric dimension of graphs previously introduced independently by Slater (Proc. 6th Southeastern Conference on Combinatorics, Graph Theory, and Computing, 549-559, 1975) and by Harary and Melter (Ars Combinatoria, 2, 191-195, 1976), and has since been investigated in several research papers. However, the exact worst-case computational complexity of computing the strong metric dimension has remained open beyond being NP-complete. In this communication, we show that the problem of computing the strong metric dimension of a graph of $n$ nodes admits a polynomial-time $2$-approximation, admits a $O^\ast\big(2^{\,0.287\,n}\big)$-time exact computation algorithm, admits a $O\big(1.2738^k+n\,k\big)$-time exact computation algorithm if the strong metric dimension is at most $k$, does not admit a polynomial time $(2-\varepsilon)$-approximation algorithm assuming the unique games conjecture is true, does not admit a polynomial time $(10\sqrt{5}-21-\varepsilon)$-approximation algorithm assuming P$\neq$NP, does not admit a $O^\ast\big(2^{o(n)}\big)$-time exact computation algorithm assuming the exponential time hypothesis is true, and does not admit a $O^\ast\big(n^{o(k)}\big)$-time exact computation algorithm if the strong metric dimension is at most $k$ assuming the exponential time hypothesis is true., Comment: revised version based on reviewer comments; to appear in Discrete Applied Mathematics

Network measures that reflect the most salient properties of complex large-scale networks are in high demand in the network research community. In this paper we adapt a combinatorial measure of negative curvature (also called hyperbolicity) to parameterized finite networks, and show that a variety of biological and social networks are hyperbolic. This hyperbolicity property has strong implications on the higher-order connectivity and other topological properties of these networks. Specifically, we derive and prove bounds on the distance among shortest or approximately shortest paths in hyperbolic networks. We describe two implications of these bounds to cross-talk in biological networks, and to the existence of central, influential neighborhoods in both biological and social networks., Comment: Physical Review E, 2014

In [1] Zawadoski introduces a banking network model in which the asset and counter-party risks are treated separately and the banks hedge their assets risks by appropriate OTC contracts. In his model, each bank has only two counter-party neighbors, a bank fails due to the counter-party risk only if at least one of its two neighbors default, and such a counter-party risk is a low probability event. Informally, the author shows that the banks will hedge their asset risks by appropriate OTC contracts, and, though it may be socially optimal to insure against counter-party risk, in equilibrium banks will {\em not} choose to insure this low probability event. In this paper, we consider the above model for more general network topologies, namely when each node has exactly 2r counter-party neighbors for some integer r>0. We extend the analysis of [1] to show that as the number of counter-party neighbors increase the probability of counter-party risk also increases, and in particular the socially optimal solution becomes privately sustainable when each bank hedges its risk to at least n/2 banks, where n is the number of banks in the network, i.e., when 2r is at least n/2, banks not only hedge their asset risk but also hedge its counter-party risk., Comment: to appear in Network Models in Economics and Finance, V. Kalyagin, P. M. Pardalos and T. M. Rassias (editors), Springer Optimization and Its Applications series, Springer, 2014

In this survey paper, we will present a number of core algorithmic questions concerning several transitive reduction problems on network that have applications in network synthesis and analysis involving cellular processes. Our starting point will be the so-called minimum equivalent digraph problem, a classic computational problem in combinatorial algorithms. We will subsequently consider a few non-trivial extensions or generalizations of this problem motivated by applications in systems biology. We will then discuss the applications of these algorithmic methodologies in the context of three major biological research questions: synthesizing and simplifying signal transduction networks, analyzing disease networks, and measuring redundancy of biological networks.

Volumetric parameterization problem refers to parameterization of both the interior and boundary of a 3D model. It is a much harder problem compared to surface parameterization where a parametric representation is worked out only for the boundary of a 3D model (which is a surface). Volumetric parameterization is typically helpful in solving complicated geometric problems pertaining to shape matching, morphing, path planning of robots, and isogeometric analysis etc. A novel method is proposed in which a volume parameterization is developed by mapping a general non-convex (genus-0) domain to its topologically equivalent convex domain. In order to achieve a continuous and bijective mapping of a domain, first we use the harmonic function to establish a potential field over the domain. The gradients of the potential values are used to track the streamlines which originate from the boundary and converge to a single point, referred to as the shape center. Each streamline approaches the shape center at a unique polar angle and an azimuthal angle . Once all the three parameters (potential value, polar angle, azimuthal angle) necessary to represent any point in the given domain are available, the domain is said to be parameterized. Using our method, given a 3D non-convex domain, we can parameterize the surface as well as the interior of the domain. The proposed method is implemented and the algorithm is tested on many standard cases to demonstrate the effectiveness., Comment: www.cadanda.com