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

Drug target identification is of significant commercial interest to pharmaceutical companies, and there is a vast amount of research done related to the topic of therapeutic target identification. Interdisciplinary research in this area involves both the biological network community and the graph algorithms community. Key steps of a typical therapeutic target identification problem include synthesizing or inferring the complex network of interactions relevant to the disease, connecting this network to the disease-specific behavior, and predicting which components are key mediators of the behavior. All of these steps involve graph theoretical or graph algorithmic aspects. In this perspective, we provide modelling and algorithmic perspectives for therapeutic target identification and highlight a number of algorithmic advances, which have gotten relatively little attention so far, with the hope of strengthening the ties between these two research communities.

Although the results are correct, it was pointed out that the results follow from some previously known results. Accordingly, this version of the paper is withdrawn by the authors., Comment: Although the results are correct, it was pointed out that the results follow from some previously known results. Accordingly, this version of the paper is withdrawn by the authors

The recent financial crisis have generated renewed interests in fragilities of global financial networks among economists and regulatory authorities. In particular, a potential vulnerability of the financial networks is the "financial contagion" process in which insolvencies of individual entities propagate through the "web of dependencies" to affect the entire system. In this paper, we formalize an extension of a financial network model originally proposed by Nier et al. for scenarios such as the OTC derivatives market, define a suitable global stability measure for this model, and perform a comprehensive empirical evaluation of this stability measure over more than 700,000 combinations of networks types and parameter combinations. Based on our evaluations, we discover many interesting implications of our evaluations of this stability measure, and derive topological properties and parameters combinations that may be used to flag the network as a possible fragile network. An interactive software FIN-STAB for computing the stability is available from the website www2.cs.uic.edu/~dasgupta/financial-simulator-files, Comment: arXiv admin note: text overlap with arXiv:1112.5687 by other authors. Prior title for this article was "Contagion in Financial Networks: Measure, Evaluation and Implications"

In this paper we explore a connection between two seemingly different problems from two different domains: the small-set expansion problem studied in unique games conjecture, and a popular community finding approach for social networks known as the modularity clustering approach. We show that a sub-exponential time algorithm for the small-set expansion problem leads to a sub-exponential time constant factor approximation for some hard input instances of the modularity clustering problem., Comment: Information Processing Letters, 2014

Threats on the stability of a financial system may severely affect the functioning of the entire economy, and thus considerable emphasis is placed on the analyzing the cause and effect of such threats. The financial crisis in the current and past decade has shown that one important cause of instability in global markets is the so-called financial contagion, namely the spreading of instabilities or failures of individual components of the network to other, perhaps healthier, components. This leads to a natural question of whether the regulatory authorities could have predicted and perhaps mitigated the current economic crisis by effective computations of some stability measure of the banking networks. Motivated by such observations, we consider the problem of defining and evaluating stabilities of both homogeneous and heterogeneous banking networks against propagation of synchronous idiosyncratic shocks given to a subset of banks. We formalize the homogeneous banking network model of Nier et al. and its corresponding heterogeneous version, formalize the synchronous shock propagation procedures, define two appropriate stability measures and investigate the computational complexities of evaluating these measures for various network topologies and parameters of interest. Our results and proofs also shed some light on the properties of topologies and parameters of the network that may lead to higher or lower stabilities., Comment: to appear in Algorithmica

It is well-known that biological and social interaction networks have a varying degree of redundancy, though a consensus of the precise cause of this is so far lacking. In this paper, we introduce a topological redundancy measure for labeled directed networks that is formal, computationally efficient and applicable to a variety of directed networks such as cellular signaling, metabolic and social interaction networks. We demonstrate the computational efficiency of our measure by computing its value and statistical significance on a number of biological and social networks with up to several thousands of nodes and edges. Our results suggest a number of interesting observations: (1) social networks are more redundant that their biological counterparts, (2) transcriptional networks are less redundant than signaling networks, (3) the topological redundancy of the C. elegans metabolic network is largely due to its inclusion of currency metabolites, and (4) the redundancy of signaling networks is highly (negatively) correlated with the monotonicity of their dynamics., Comment: 18 pages

In an implicit combinatorial optimization problem, the constraints are not enumerated explicitly but rather stated implicitly through equations, other constraints or auxiliary algorithms. An important subclass of such problems is the implicit set cover (or, equivalently, hitting set) problem in which the sets are not given explicitly but rather defined implicitly For example, the well-known minimum feedback arc set problem is such a problem. In this paper, we consider such a cover problem that arises in the study of wild populations in biology in which the sets are defined implicitly via the Mendelian constraints and prove approximability results for this problem., Comment: 11 pages

The understanding of molecular cell biology requires insight into the structure and dynamics of networks that are made up of thousands of interacting molecules of DNA, RNA, proteins, metabolites, and other components. One of the central goals of systems biology is the unraveling of the as yet poorly characterized complex web of interactions among these components. This work is made harder by the fact that new species and interactions are continuously discovered in experimental work, necessitating the development of adaptive and fast algorithms for network construction and updating. Thus, the "reverse-engineering" of networks from data has emerged as one of the central concern of systems biology research. A variety of reverse-engineering methods have been developed, based on tools from statistics, machine learning, and other mathematical domains. In order to effectively use these methods, it is essential to develop an understanding of the fundamental characteristics of these algorithms. With that in mind, this chapter is dedicated to the reverse-engineering of biological systems. Specifically, we focus our attention on a particular class of methods for reverse-engineering, namely those that rely algorithmically upon the so-called "hitting-set" problem, which is a classical combinatorial and computer science problem, Each of these methods utilizes a different algorithm in order to obtain an exact or an approximate solution of the hitting set problem. We will explore the ultimate impact that the alternative algorithms have on the inference of published in silico biological networks., Comment: 15 pages; in Algorithms in Computational Molecular Biology: Techniques, Approaches and Applications, M. Elloumi and A. Zomaya (editors), John Wiley & Sons, Inc., January 2011

In this paper, we consider the weighted online set k-multicover problem. In this problem, we have a universe V of elements, a family S of subsets of V with a positive real cost for every set in S and a "coverage factor" (positive integer) k. A subset of elements are presented online in an arbitrary order. When each element, say i, is presented, we are also told the collection of all (at least k) sets and their costs to which i belongs and we need to select additional sets from these sets containing i, if necessary, such that our collection of selected sets contains at least k sets that contain the element i. The goal is to minimize the total cost of the selected sets (our algorithm and competitive ratio bounds can be extended to the case when a set can be selected at most a pre-specified number of times instead of just once; we do not report these extensions for simplicity and also because they have no relevance to the biological applications that motivated our work). In this paper, we describe a new randomized algorithm for the online multicover problem based on a randomized version of the winnowing approach of Littlestone. This algorithm generalizes and improves some earlier results by N. Alon, B. Awerbuch, Y. Azar, N. Buchbinder, and J. Naor. We also discuss lower bounds on competitive ratios for deterministic algorithms for general $k$., Comment: 22 pages

A traditionally desired goal when designing auction mechanisms is incentive compatibility, i.e., ensuring that bidders fare best by truthfully reporting their preferences. A complementary goal, which has, thus far, received significantly less attention, is to preserve privacy, i.e., to ensure that bidders reveal no more information than necessary. We further investigate and generalize the approximate privacy model for two-party communication recently introduced by Feigenbaum et al.[8]. We explore the privacy properties of a natural class of communication protocols that we refer to as "dissection protocols". Dissection protocols include, among others, the bisection auction in [9,10] and the bisection protocol for the millionaires problem in [8]. Informally, in a dissection protocol the communicating parties are restricted to answering simple questions of the form "Is your input between the values \alpha and \beta (under a predefined order over the possible inputs)?". We prove that for a large class of functions, called tiling functions, which include the 2nd-price Vickrey auction, there always exists a dissection protocol that provides a constant average-case privacy approximation ratio for uniform or "almost uniform" probability distributions over inputs. To establish this result we present an interesting connection between the approximate privacy framework and basic concepts in computational geometry. We show that such a good privacy approximation ratio for tiling functions does not, in general, exist in the worst case. We also discuss extensions of the basic setup to more than two parties and to non-tiling functions, and provide calculations of privacy approximation ratios for two functions of interest., Comment: to appear in Theoretical Computer Science (series A)

In this paper, we consider approximability issues of the following four problems: triangle packing, full sibling reconstruction, maximum profit coverage and 2-coverage. All of them are generalized or specialized versions of set-cover and have applications in biology ranging from full-sibling reconstructions in wild populations to biomolecular clusterings; however, as this paper shows, their approximability properties differ considerably. Our inapproximability constant for the triangle packing problem improves upon the previous results; this is done by directly transforming the inapproximability gap of Haastad for the problem of maximizing the number of satisfied equations for a set of equations over GF(2) and is interesting in its own right. Our approximability results on the full siblings reconstruction problems answers questions originally posed by Berger-Wolf et al. and our results on the maximum profit coverage problem provides almost matching upper and lower bounds on the approximation ratio, answering a question posed by Hassin and Or., Comment: 25 pages

Given a graph of interactions, a module (also called a community or cluster) is a subset of nodes whose fitness is a function of the statistical significance of the pairwise interactions of nodes in the module. The topic of this paper is a model-based community finding approach, commonly referred to as modularity clustering, that was originally proposed by Newman and has subsequently been extremely popular in practice. Various heuristic methods are currently employed for finding the optimal solution. However, the exact computational complexity of this approach is still largely unknown. To this end, we initiate a systematic study of the computational complexity of modularity clustering. Due to the specific quadratic nature of the modularity function, it is necessary to study its value on sparse graphs and dense graphs separately. Our main results include a (1+\eps)-inapproximability for dense graphs and a logarithmic approximation for sparse graphs. We make use of several combinatorial properties of modularity to get these results. These are the first non-trivial approximability results beyond the previously known NP-hardness results., Comment: Journal of Computer and System Sciences, 2012

Internet advertising is a sophisticated game in which the many advertisers "play" to optimize their return on investment. There are many "targets" for the advertisements, and each "target" has a collection of games with a potentially different set of players involved. In this paper, we study the problem of how advertisers allocate their budget across these "targets". In particular, we focus on formulating their best response strategy as an optimization problem. Advertisers have a set of keywords ("targets") and some stochastic information about the future, namely a probability distribution over scenarios of cost vs click combinations. This summarizes the potential states of the world assuming that the strategies of other players are fixed. Then, the best response can be abstracted as stochastic budget optimization problems to figure out how to spread a given budget across these keywords to maximize the expected number of clicks. We present the first known non-trivial poly-logarithmic approximation for these problems as well as the first known hardness results of getting better than logarithmic approximation ratios in the various parameters involved. We also identify several special cases of these problems of practical interest, such as with fixed number of scenarios or with polynomial-sized parameters related to cost, which are solvable either in polynomial time or with improved approximation ratios. Stochastic budget optimization with scenarios has sophisticated technical structure. Our approximation and hardness results come from relating these problems to a special type of (0/1, bipartite) quadratic programs inherent in them. Our research answers some open problems raised by the authors in (Stochastic Models for Budget Optimization in Search-Based Advertising, Algorithmica, 58 (4), 1022-1044, 2010)., Comment: FINAL version

We study the problem of computing a minimum equivalent digraph (also known as the problem of computing a strong transitive reduction) and its maximum objective function variant, with two types of extensions. First, we allow to declare a set $D\subset E$ and require that a valid solution $A$ satisfies $D\subset A$ (it is sometimes called transitive reduction problem). In the second extension (called $p$-ary transitive reduction), we have integer edge labeling and we view two paths as equivalent if they have the same beginning, ending and the sum of labels modulo $p$. A solution $A\subseteq E$ is valid if it gives an equivalent path for every original path. For all problems we establish the following: polynomial time minimization of $|A|$ within ratio 1.5, maximization of $|E-A|$ within ratio 2, MAX-SNP hardness even of the length of simple cycles is limited to 5. Furthermore, we believe that the combinatorial technique behind the approximation algorithm for the minimization version might be of interest to other graph connectivity problems as well.

A useful approach to the mathematical analysis of large-scale biological networks is based upon their decompositions into monotone dynamical systems. This paper deals with two computational problems associated to finding decompositions which are optimal in an appropriate sense. In graph-theoretic language, the problems can be recast in terms of maximal sign-consistent subgraphs. The theoretical results include polynomial-time approximation algorithms as well as constant-ratio inapproximability results. One of the algorithms, which has a worst-case guarantee of 87.9 percent from optimality, is based on the semidefinite programming relaxation approach of Goemans-Williamson. The algorithm was implemented and tested on a Drosophila segmentation network and an Epidermal Growth Factor Receptor pathway model, and it was found to perform close to optimally., Comment: 34 pages, 5 Postscript figures

String barcoding is a recently introduced technique for genomic-based identification of microorganisms. In this paper we describe the engineering of highly scalable algorithms for robust string barcoding. Our methods enable distinguisher selection based on whole genomic sequences of hundreds of microorganisms of up to bacterial size on a well-equipped workstation, and can be easily parallelized to further extend the applicability range to thousands of bacterial size genomes. Experimental results on both randomly generated and NCBI genomic data show that whole-genome based selection results in a number of distinguishers nearly matching the information theoretic lower bounds for the problem.

Circular permutation connects the N and C termini of a protein and concurrently cleaves elsewhere in the chain, providing an important mechanism for generating novel protein fold and functions. However, their in genomes is unknown because current detection methods can miss many occurances, mistaking random repeats as circular permutation. Here we develop a method for detecting circularly permuted proteins from structural comparison. Sequence order independent alignment of protein structures can be regarded as a special case of the maximum-weight independent set problem, which is known to be computationally hard. We develop an efficient approximation algorithm by repeatedly solving relaxations of an appropriate intermediate integer programming formulation, we show that the approximation ratio is much better then the theoretical worst case ratio of $r = 1/4$. Circularly permuted proteins reported in literature can be identified rapidly with our method, while they escape the detection by publicly available servers for structural alignment., Comment: 5 pages, 3 figures, Accepted by IEEE-EMBS 2004 Conference Proceedings

Two general algorithms based on opportunity costs are given for approximating a revenue-maximizing set of bids an auctioneer should accept, in a combinatorial auction in which each bidder offers a price for some subset of the available goods and the auctioneer can only accept non-intersecting bids. Since this problem is difficult even to approximate in general, the algorithms are most useful when the bids are restricted to be connected node subsets of an underlying object graph that represents which objects are relevant to each other. The approximation ratios of the algorithms depend on structural properties of this graph and are small constants for many interesting families of object graphs. The running times of the algorithms are linear in the size of the bid graph, which describes the conflicts between bids. Extensions of the algorithms allow for efficient processing of additional constraints, such as budget constraints that associate bids with particular bidders and limit how many bids from a particular bidder can be accepted.