BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Alexandru Popa

Alexandru Popa contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsComputational ComplexityFormal Languages and Automata TheoryProgramming LanguagesSocial and Information Networks

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
6works
0followers
5topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

6 published item(s)

preprint2020arXiv

A decision support system for optimizing the cost of social distancing in order to stop the spread of COVID-19

Currently there are many attempts around the world to use computers, smartphones, tablets and other electronic devices in order to stop the spread of COVID-19. Most of these attempts focus on collecting information about infected people, in order to help healthy people avoid contact with them. However, social distancing decisions are still taken by the governments empirically. That is, the authorities do not have an automated tool to recommend which decisions to make in order to maximize social distancing and to minimize the impact for the economy. In this paper we address the aforementioned problem and we design an algorithm that provides social distancing methods (i.e., what schools, shops, factories, etc. to close) that are efficient (i.e., that help reduce the spread of the virus) and have low impact on the economy. On short: a) we propose several models (i.e., combinatorial optimization problems); b) we show some theoretical results regarding the computational complexity of the formulated problems; c) we give an algorithm for the most complex of the previously formulated problems; d) we implement and test our algorithm; and e) we show an integer linear program formulation for our problem.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Complexity of Computing the Anti-Ramsey Numbers for Paths

The anti-Ramsey numbers are a fundamental notion in graph theory, introduced in 1978, by Erd\" os, Simonovits and S\' os. For given graphs $G$ and $H$ the \emph{anti-Ramsey number} $\textrm{ar}(G,H)$ is defined to be the maximum number $k$ such that there exists an assignment of $k$ colors to the edges of $G$ in which every copy of $H$ in $G$ has at least two edges with the same color. There are works on the computational complexity of the problem when $H$ is a star. Along this line of research, we study the complexity of computing the anti-Ramsey number $\textrm{ar}(G,P_k)$, where $P_k$ is a path of length $k$. First, we observe that when $k = Ω(n)$, the problem is hard; hence, the challenging part is the computational complexity of the problem when $k$ is a fixed constant. We provide a characterization of the problem for paths of constant length. Our first main contribution is to prove that computing $\textrm{ar}(G,P_k)$ for every integer $k>2$ is NP-hard. We obtain this by providing several structural properties of such coloring in graphs. We investigate further and show that approximating $\textrm{ar}(G,P_3)$ to a factor of $n^{-1/2 - ε}$ is hard already in $3$-partite graphs, unless P=NP. We also study the exact complexity of the precolored version and show that there is no subexponential algorithm for the problem unless ETH fails for any fixed constant $k$. Given the hardness of approximation and parametrization of the problem, it is natural to study the problem on restricted graph families. We introduce the notion of color connected coloring and employing this structural property. We obtain a linear time algorithm to compute $\textrm{ar}(G,P_k)$, for every integer $k$, when the host graph, $G$, is a tree.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

The min-max edge q-coloring problem

In this paper we introduce and study a new problem named \emph{min-max edge $q$-coloring} which is motivated by applications in wireless mesh networks. The input of the problem consists of an undirected graph and an integer $q$. The goal is to color the edges of the graph with as many colors as possible such that: (a) any vertex is incident to at most $q$ different colors, and (b) the maximum size of a color group (i.e. set of edges identically colored) is minimized. We show the following results: 1. Min-max edge $q$-coloring is NP-hard, for any $q \ge 2$. 2. A polynomial time exact algorithm for min-max edge $q$-coloring on trees. 3. Exact formulas of the optimal solution for cliques and almost tight bounds for bicliques and hypergraphs. 4. A non-trivial lower bound of the optimal solution with respect to the average degree of the graph. 5. An approximation algorithm for planar graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Hardness and Approximation of The Asynchronous Border Minimization Problem

We study a combinatorial problem arising from microarrays synthesis. The synthesis is done by a light-directed chemical process. The objective is to minimize unintended illumination that may contaminate the quality of experiments. Unintended illumination is measured by a notion called border length and the problem is called Border Minimization Problem (BMP). The objective of the BMP is to place a set of probe sequences in the array and find an embedding (deposition of nucleotides/residues to the array cells) such that the sum of border length is minimized. A variant of the problem, called P-BMP, is that the placement is given and the concern is simply to find the embedding. Approximation algorithms have been previously proposed for the problem but it is unknown whether the problem is NP-hard or not. In this paper, we give a thorough study of different variations of BMP by giving NP-hardness proofs and improved approximation algorithms. We show that P-BMP, 1D-BMP, and BMP are all NP-hard. Contrast with the previous result that 1D-P-BMP is polynomial time solvable, the interesting implications include (i) the array dimension (1D or 2D) differentiates the complexity of P-BMP; (ii) for 1D array, whether placement is given differentiates the complexity of BMP; (iii) BMP is NP-hard regardless of the dimension of the array. Another contribution of the paper is improving the approximation for BMP from $O(n^{1/2} \log^2 n)$ to $O(n^{1/4} \log^2 n)$, where $n$ is the total number of sequences.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Restricted Common Superstring and Restricted Common Supersequence

The {\em shortest common superstring} and the {\em shortest common supersequence} are two well studied problems having a wide range of applications. In this paper we consider both problems with resource constraints, denoted as the Restricted Common Superstring (shortly \textit{RCSstr}) problem and the Restricted Common Supersequence (shortly \textit{RCSseq}). In the \textit{RCSstr} (\textit{RCSseq}) problem we are given a set $S$ of $n$ strings, $s_1$, $s_2$, $\ldots$, $s_n$, and a multiset $t = \{t_1, t_2, \dots, t_m\}$, and the goal is to find a permutation $π: \{1, \dots, m\} \to \{1, \dots, m\}$ to maximize the number of strings in $S$ that are substrings (subsequences) of $π(t) = t_{π(1)}t_{π(2)}...t_{π(m)}$ (we call this ordering of the multiset, $π(t)$, a permutation of $t$). We first show that in its most general setting the \textit{RCSstr} problem is {\em NP-complete} and hard to approximate within a factor of $n^{1-ε}$, for any $ε> 0$, unless P = NP. Afterwards, we present two separate reductions to show that the \textit{RCSstr} problem remains NP-Hard even in the case where the elements of $t$ are drawn from a binary alphabet or for the case where all input strings are of length two. We then present some approximation results for several variants of the \textit{RCSstr} problem. In the second part of this paper, we turn to the \textit{RCSseq} problem, where we present some hardness results, tight lower bounds and approximation algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Undecidability Results for Finite Interactive Systems

A new approach to the design of massively parallel and interactive programming languages has been recently proposed using rv-systems (interactive systems with registers and voices) and Agapia programming. In this paper we present a few theoretical results on FISs (finite interactive systems), the underlying mechanism used for specifying control and interaction in these systems. First, we give a proof for the undecidability of the emptiness problem for FISs, by reduction to the Post Correspondence Problem. Next, we use the construction in this proof to get other undecidability results, e.g., for the accessibility of a transition in a FIS, or for the finiteness of the language recognized by a FIS. Finally, we present a simple proof of the equivalence between FISs and tile systems, making explicit that they precisely capture recognizable two-dimensional languages.

0 citations0 reviewsNo code linkedOpen access