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.

Establishing family relationships, such as parentage and sibling relationships, is fundamental in biological research, especially in wild species, as they are often important to understanding evolutionary, ecological, and behavioral processes. Because it is commonly impossible to determine familial relationships from field observations alone, the reconstruction of sibling relationships often depends on informative genetic markers coupled with accurate sibling reconstruction algorithms. Most studies in the literature reconstruct sibling relationships using methods that are based on either statistical analyses (i.e., likelihood estimation) or combinatorial concepts (i.e., Mendelian inheritance laws) of genetic data. We present a novel computational framework that integrates both combinatorial concepts and statistical analyses into one sibling reconstruction optimization model. To solve this integrated model, we propose a column-generation approach with a branch-and-price method. Under the assumption of parsimonious reconstruction, the master problem is to find the minimum set of sibling groups to cover the tested population. Pricing subproblems, which include both statistical similarity and combinatorial concepts of genetic data, are iteratively solved to generate high-quality sibling group candidates. Tested on real biological data sets, our approach efficiently provides reconstruction results that are more accurate than those provided by other state-of-the-art reconstruction algorithms.

The emergence of numerous online sources about local services presents a need for more automatic yet accurate data integration techniques. Local services are georeferenced objects and can be queried by their locations on a map, for instance, neighborhoods. Typical local service queries (e.g., “French Restaurant in The Loop”) include not only information about “what” (“French Restaurant”) a user is searching for (such as cuisine) but also “where” information, such as neighborhood (“The Loop”). In this article, we address three key problems: query translation, result merging and ranking. Most local search engines provide a (hierarchical) organization of (large) cities into neighborhoods. A neighborhood in one local search engine may correspond to sets of neighborhoods in other local search engines. These make the query translation challenging. To provide an integrated access to the query results returned by the local search engines, we need to combine the results into a single list of results. Our contributions include: (1) An integration algorithm for neighborhoods. (2) A very effective business listing resolution algorithm. (3) A ranking algorithm that takes into consideration the user criteria, user ratings and rankings. We have created a prototype system, Yumi, over local search engines in the restaurant domain. The restaurant domain is a representative case study for the local services. We conducted a comprehensive experimental study to evaluate Yumi. A prototype version of Yumi is available online.

We present YumiInt a deep Web integration system for local search engines for Geo-referenced objects. YumiInt consists of two systems: YumiDev and YumiMeta. YumiDev is an off-line integration system that builds the key components (e.g., query translation and entity resolution) of YumiMeta. YumiMeta is the Web application to which users post queries. It translates queries to multiple sources and gets back aggregated lists of results. We present the two systems in this paper.

The proliferation of mobile devices, location-based services and embedded wireless sensors has given rise to applications that seek to improve the efficiency of the transportation system. In particular, new applications are already available that help travelers to find parking in urban settings by conveying the parking slot availability near the desired destinations of travelers on their mobile devices.

In this paper we present a model of spatially located mobile agents and static resources, in which the agents are looking to obtain one of the resources while minimizing their costs to obtain the resource. The proliferation of mobile devices, location-based services and embedded wireless sensors has given rise to applications that could help the mobile agents have updated information of the location of the resources they are looking for. Nevertheless, while engaged in driving, travelers are better suited being guided to an ideal resource, rather than looking at a map and deciding which available resource to visit. Then the question of how an application should choose this ideal resource, to guide the agent towards it, becomes relevant. In this work we develop algorithms that are designed to guide users to these resources. They use a gravitational approach to guide a mobile agent through a road network in order to find this ideal resource. The performance of the algorithms is evaluated through simulations.

With the proliferation of location-based services, mobile devices, and embedded wireless sensors, more and more applications are being developed to improve the efficiency of the transportation system. In particular, new applications are arising to help vehicles locate open parking slots. Nevertheless, while engaged in driving, travelers are better suited being guided to an ideal parking slot, than looking at a map and choosing which slot to go to. Then the question of how an application should choose this ideal parking slot becomes relevant. Vehicular parking can be viewed as vehicles (players) competing for parking slots (resources with different costs). Based on this competition, we present a game-theoretic framework to analyze parking situations. We introduce and analyze parking slot assignment games and present algorithms that choose parking slots ideally in competitive parking simulations. We also present algorithms for incomplete information contexts and show how these algorithms outperform even algorithms with complete information in some cases.

With the proliferation of location-based services, mobile devices, and embedded wireless sensors, more and more applications are being developed to improve the efficiency of the transportation system. In particular, new applications are arising to help vehicles locate open parking spaces. Nevertheless, while engaged in driving, travelers are better suited being guided to a particular and ideal parking slot, than looking at a map and choosing which spot to go to. Then the question of how an application should choose this ideal parking spot becomes relevant.

With improved tools for collecting genetic data from natural and experimental populations, new opportunities arise to study fundamental biological processes, including behavior, mating systems, adaptive trait evolution, and dispersal patterns. Full use of the newly available genetic data often depends upon reconstructing genealogical relationships of individual organisms, such as sibling reconstruction. This paper presents a new optimization framework for sibling reconstruction from single generation microsatellite genetic data. Our framework is based on assumptions of parsimony and combinatorial concepts of Mendel's inheritance rules. Here, we develop a novel optimization model for sibling reconstruction as a large-scale mixed-integer program (MIP), shown to be a generalization of the set covering problem. We propose a new heuristic approach to efficiently solve this large-scale optimization problem. We test our approach on real biological data as presented in other studies as well as simulated data, and compare our results with other state-of-the-art sibling reconstruction methods. The empirical results show that our approaches are very efficient and outperform other methods while providing the most accurate solutions for two benchmark data sets. The results suggest that our framework can be used as an analytical and computational tool for biologists to better study ecological and evolutionary processes involving knowledge of familial relationships in a wide variety of biological systems.

UNLABELLED: We present a software for combined synthesis, inference and simplification of signal transduction networks. The main idea of our method lies in representing observed indirect causal relationships as network paths and using techniques from combinatorial optimization to find the sparsest graph consistent with all experimental observations. We illustrate the biological usability of our software by applying it to a previously published signal transduction network and by using it to synthesize and simplify a novel network corresponding to activation-induced cell death in large granular lymphocyte leukemia. AVAILABILITY: NET-SYNTHESIS is freely downloadable from http://www.cs.uic.edu/~dasgupta/network-synthesis/

BACKGROUND: Identifying structurally similar proteins with different chain topologies can aid studies in homology modeling, protein folding, protein design, and protein evolution. These include circular permuted protein structures, and the more general cases of non-cyclic permutations between similar structures, which are related by non-topological rearrangement beyond circular permutation. We present a method based on an approximation algorithm that finds sequence-order independent structural alignments that are close to optimal. We formulate the structural alignment problem as a special case of the maximum-weight independent set problem, and solve this computationally intensive problem approximately by iteratively solving relaxations of a corresponding integer programming problem. The resulting structural alignment is sequence order independent. Our method is also insensitive to insertions, deletions, and gaps. RESULTS: Using a novel similarity score and a statistical model for significance p-value, we are able to discover previously unknown circular permuted proteins between nucleoplasmin-core protein and auxin binding protein, between aspartate rasemase and 3-dehydrogenate dehydralase, as well as between migration inhibition factor and arginine repressor which involves an additional strand-swapping. We also report the finding of non-cyclic permuted protein structures existing in nature between AML1/core binding factor and ribofalvin synthase. Our method can be used for large scale alignment of protein structures regardless of the topology. CONCLUSION: The approximation algorithm introduced in this work can find good solutions for the problem of protein structure alignment. Furthermore, this algorithm can detect topological differences between two spatially similar protein structures. The alignment between MIF and the arginine repressor demonstrates our algorithm's ability to detect structural similarities even when spatial rearrangement of structural units has occurred. The effectiveness of our method is also demonstrated by the discovery of previously unknown circular permutations. In addition, we report in this study the finding of a naturally occurring non-cyclic permuted protein between AML1/Core Binding Factor chain F and riboflavin synthase chain A.

In this paper, we study the problem of motif discoveries in unaligned DNA and protein sequences. The problem of motif identification in DNA and protein sequences has been studied for many years in the literature. Major hurdles at this point include computational complexity and reliability of the search algorithms. We propose a self-organizing neural network structure for solving the problem of motif identification in DNA and protein sequences. Our network contains several layers, with each layer performing classifications at different levels. The top layer divides the input space into a small number of regions and the bottom layer classifies all input patterns into motifs and nonmotif patterns. Depending on the number of input patterns to be classified, several layers between the top layer and the bottom layer are needed to perform intermediate classifications. We maintain a low computational complexity through the use of the layered structure so that each pattern's classification is performed with respect to a small subspace of the whole input space. Our self-organizing neural network will grow as needed (e.g., when more motif patterns are classified). It will give the same amount of attention to each input pattern and will not omit any potential motif patterns. Finally, simulation results show that our algorithm outperforms existing algorithms in certain aspects. In particular, simulation results show that our algorithm can identify motifs with more mutations than existing algorithms. Our algorithm works well for long DNA sequences as well.

Summary: DNA-BAR is a software package for selecting DNA probes (henceforth referred to as distinguishers) that can be used in genomic-based identification of microorganisms. Given the genomic sequences of the microorganisms, DNA-BAR finds a near-minimum number of distinguishers yielding a distinct hybridization pattern for each microorganism. Selected distinguishers satisfy user specified bounds on length, melting temperature and GC content, as well as redundancy and cross-hybridization constraints. Availability: DNA-BAR can be used online through the web interface provided at http://dna.engr.uconn.edu/~software/DNA-BAR/. The open source C code, released under the GNU General Public License, is also available at the above address. Contact: [email protected]

We prove the following upper and lower bounds on the exact size of binary space partition (BSP) trees for a set of n isothetic rectangles in the plane: An upper bound of 3n-1 in general, and an upper bound of 2n-1 if the rectangles tile the underlying space. This improves the upper bounds of 4n in [V. Hai Nguyen and P. Widmayer, Binary Space Partitions for Sets of Hyperrectangles, Lecture Notes in Comput. Sci. 1023, Springer-Verlag, Berlin, 1995; F. d'Amore and P. G. Franciosa, Inform. Process. Lett., 44 (1992), pp. 255--259]. A BSP satisfying the upper bounds can be constructed in O(n log n) time. A worst-case lower bound of 2n-o(n) in general, and $\frac{3n}{2}-o(n)$ if the rectangles form a tiling. The BSP tree is one of the most popular data structures in computational geometry, and hence even "small" factor improvements of $\frac{4}{3}$ or 2 on the previously known upper bounds that we show improve the performances of applications relying on the BSP tree. As an illustration, we present improved approximation algorithms for certain dual rectangle tiling problems using our upper bounds on the size of the BSP trees.

We consider the problem of off-line throughput maximization for job scheduling on one or more machines, where each job has a release time, a deadline and a profit. Most of the versions of the problem discussed here were already treated by Bar-Noy et al.(Proc. 31st ACM STOC, 622-631, 1999). Our main contribution is to provide algorithms that do not use linear programming, are simple and much faster than the corresponding ones proposed in Bar-Noy et al., while either having the same quality of approximation or improving it. More precisely, compared to the results of in Bar-Noy et al., our pseudo-polynomial algorithm for multiple unrelated machines and all of our strongly-polynomial algorithms have better performance ratios, all of our algorithms run much faster, are combinatorial in nature and avoid linear programming. Finally, we show that algorithms with better performance ratios than 2 are possible if the stretch factors of the jobs are bounded.

The paper studies the computational complexity and approximation algorithms for a new evolutionary distance between multi-chromosomal genomes introduced recently by Ferretti, Nadeau and Sankoff. Here, a chromosome is represented as a set of genes and a genome is a collections of chromosomes. The syntenic distance between two genomes is defined as the minimum number of translocations, fusions and fissions required to transform one genome into the other. We prove that computing the syntenic distance is NP-hard and give a simple approximation algorithm with performance ratio 2. For the case when an upper bound d on the syntenic distance is known, we show that an optimal syntenic sequence can be found in O(nk + 2o(d2)) time, where n and k are the number of chromosomes in the two given genomes. Next, we show that if the set of operations for transforming a genome is significantly restricted, we can nevertheless find a solution that performs at most O(log d) additional moves, where d is the number of moves performed by the unrestricted optimum. This result should help in the design of approximation algorithms. Finally, we investigate the median problem: Given three genomes, construct a genome minimizing the total syntenic distance to the three given genomes and compute the corresponding median distance. The problem has application in the inference of phytogenies based on the syntenic distance. We prove that the problem is NP-hard and design a polynomial time approximation algorithm with a performance ratio of 4+ε for any constant ε > 0.

Article Free Access Share on On the complexity and approximation of syntenic distance Authors: B. DasGupta Department of Computer Science, Rutgers University, Camden, NJ Department of Computer Science, Rutgers University, Camden, NJView Profile , T. Jiang Department of Computer Science, McMaster University, Hamilton, Ontario L8S 4K1, Canada Department of Computer Science, McMaster University, Hamilton, Ontario L8S 4K1, CanadaView Profile , S. Kannan Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PAView Profile , M. Li Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong Department of Computer Science, City University of Hong Kong, Kowloon, Hong KongView Profile , Z. Sweedyk Department of Computer and Information Sciences, University of Pennsylvania, Philadelphia, PA Department of Computer and Information Sciences, University of Pennsylvania, Philadelphia, PAView Profile Authors Info & Claims RECOMB '97: Proceedings of the first annual international conference on Computational molecular biologyJanuary 1997 Pages 99–108https://doi.org/10.1145/267521.267536Published:19 January 1997Publication History 6citation243DownloadsMetricsTotal Citations6Total Downloads243Last 12 Months11Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We show that neural networks with three-times continuously differentiable activation functions are capable of computing a certain family of n-bit boolean functions with two gates, whereas networks composed of binary threshold functions require at least omega(log n) gates. Thus, for a large class of activation functions, analog neural networks can be more powerful than discrete neural networks, even when computing Boolean functions.

Recurrent perceptron classifiers generalize the usual perceptron model. They correspond to linear transformations of input vectors obtained by means of "autoregressive moving-average schemes", or infinite impulse response filters, and take into account those correlations and dependences among input coordinates which arise from linear digital filtering. This paper provides tight bounds on the sample complexity associated to the fitting of such models to experimental data. The results are expressed in the context of the theory of probably approximately correct (PAC) learning.

Deals with computational issues of loading a fixed-architecture neural network with a set of positive and negative examples. This is the first result on the hardness of loading a simple three-node architecture which does not consist of the binary-threshold neurons, but rather utilizes a particular continuous activation function, commonly used in the neural-network literature. The authors observe that the loading problem is polynomial-time if the input dimension is constant. Otherwise, however, any possible learning algorithm based on particular fixed architectures faces severe computational barriers. Similar theorems have already been proved by Megiddo and by Blum and Rivest, to the case of binary-threshold networks only. The authors' theoretical results lend further suggestion to the use of incremental (architecture-changing) techniques for training networks rather than fixed architectures. Furthermore, they imply hardness of learnability in the probably approximately correct sense as well.

This paper deals with learnability of concept classes defined by neural networks, showing the hardness of PAC-learning (in the complexity, not merely information-theoretic sense) for networks with a particular class of activation. The obstruction lies not with the VC dimension, which is known to grow slowly; instead, the result follows the fact that the loading problem is NP-complete. (The complexity scales badly with input dimension; the loading problem is polynomial-time if the input dimension is constant.) Similar and well-known theorems had already been proved by Megiddo and by Blum and Rivest, for binary-threshold networks. It turns out the general problem for continuous sigmoidal-type functions, as used in practical applications involving steepest descent, is not NP-hard—there are “sigmoidals” for which the problem is in fact trivial—so it is an open question to determine what properties of the activation function cause difficulties. Ours is the first result on the hardness of loading networks which do not consist of binary neurons; we employ a piecewise-linear activation function that has been used in the neural network literature. Our theoretical results lend further justification to the use of incremental (architecture-changing) techniques for training networks.