Search for: All records

Discrete optimization problems arise in many biological contexts and, in many cases, we seek to make inferences from the optimal solutions. However, the number of optimal solutions is frequently very large and making inferences from any single solution may result in conclusions that are not supported by other optimal solutions. We describe a general approach for efficiently (polynomial time) and exactly (without sampling) computing statistics on the space of optimal solutions. These statistics provide insights into the space of optimal solutions that can be used to support the use of a single optimum (e.g., when the optimal solutions are similar) or justify the need for selecting multiple optima (e.g., when the solution space is large and diverse) from which to make inferences. We demonstrate this approach on two well-known problems and identify the properties of these problems that make them amenable to this method. 

Birkhoff’s representation theorem defines a bijection between elements of a distributive lattice L and the family of upper sets of an associated poset B. When elements of L are the stable matchings in an instance of Gale and Shapley’s marriage model, Irving et al. showed how to use B to devise a combinatorial algorithm for maximizing a linear function over the set of stable matchings. In this paper, we introduce a general property of distributive lattices, which we term as affine representability, and show its role in efficiently solving linear optimization problems over the elements of a distributive lattice, as well as describing the convex hull of the characteristic vectors of lattice elements. We apply this concept to the stable matching model with path-independent quotafilling choice functions, thus giving efficient algorithms and a compact polyhedral description for this model. To the best of our knowledge, this model generalizes all models from the literature for which similar results were known, and our paper is the first that proposes efficient algorithms for stable matchings with choice functions, beyond extension of the Deferred Acceptance algorithm. 

Cyberattacks and malware infestation are issues that surround most operating systems (OS) these days. In smartphones, Android OS is more susceptible to malware infection. Although Android has introduced several mechanisms to avoid cyberattacks, including Google Play Protect, dynamic permissions, and sign-in control notifications, cyberattacks on Android-based phones are prevalent and continuously increasing. Most malware apps use critical permissions to access resources and data to compromise smartphone security. One of the key reasons behind this is the lack of knowledge for the usage of permissions in users. In this paper, we introduce Permission-Educator, a cloud-based service to educate users about the permissions associated with the installed apps in an Android-based smartphone. We developed an Android app as a client that allows users to categorize the installed apps on their smartphones as system or store apps. The user can learn about permissions for a specific app and identify the app as benign or malware through the interaction of the client app with the cloud service. We integrated the service with a web server that facilitates users to upload any Android application package file, i.e. apk, to extract information regarding the Android app and display it to the user.