Frontiers in Algorithmics

Frontmatter

On the Complexity of Minimizing the Total Calibration Cost

Abstract

Bender et al. (SPAA 2013) proposed a theoretical framework for testing in contexts where safety mistakes must be avoided. Testing in such a context is made by machines that need to be often calibrated. Since calibrations have non negligible cost, it is important to study policies minimizing the calibration cost while performing all the necessary tests. We focus on the single-machine setting and we study the complexity status of different variants of the problem. First, we extend the model by considering that the jobs have arbitrary processing times and that the preemption of jobs is allowed. For this case, we propose an optimal polynomial time algorithm. Then, we study the case where there is many types of calibrations with different lengths and costs. We prove that the problem becomes NP-hard for arbitrary processing times even when the preemption of the jobs is allowed. Finally, we focus on the case of unit-time jobs and we show that a more general problem, where the recalibration of the machine is not instantaneous, can be solved in polynomial time.

Eric Angel, Evripidis Bampis, Vincent Chau, Vassilis Zissimopoulos

On the Fixed-Parameter Tractability of Some Matching Problems Under the Color-Spanning Model

Abstract

Given a set of n points P in the plane, each colored with one of the t given colors, a color-spanning set \(S\subset P\) is a subset of t points with distinct colors. The minimum diameter color-spanning set (MDCS) is a color-spanning set whose diameter is minimum (among all color-spanning sets of P). Somehow symmetrically, the largest closest pair color-spanning set (LCPCS) is a color-spanning set whose closest pair is the largest (among all color-spanning sets of P). Both MDCS and LCPCS have been shown to be NP-complete, but whether they are fixed-parameter tractable (FPT) when t is a parameter are still open. (Formally, the problem whether MDCS is FPT was posed by Fleischer and Xu in 2010.) Motivated by this question, we consider the FPT tractability of some matching problems under this color-spanning model, where \(t=2k\) is the parameter. The results are summarized as follows: (1) MinSum Matching Color-Spanning Set, namely, computing a matching of 2k points with distinct colors such that their total edge length is minimized, is FPT; (2) MaxMin Matching Color-Spanning Set, namely, computing a matching of 2k points with distinct colors such that the minimum edge length is maximized, is FPT; (3) MinMax Matching Color-Spanning Set, namely, computing a matching of 2k points with distinct colors such that the maximum edge length is minimized, is FPT; and (4) k-Multicolored Independent Matching, namely, computing a matching of 2k vertices in a graph such that the vertices of the edges in the matching do not share common edges in the graph, is W[1]-hard. With (2), we show that LCPCS is in fact FPT.

Sergey Bereg, Feifei Ma, Wencheng Wang, Jian Zhang, Binhai Zhu

The Complexity of Finding (Approximate Sized) Distance-d Dominating Set in Tournaments

Abstract

A tournament is an orientation of a complete graph. For a positive integer d, a distance-d dominating set in a tournament is a subset S of vertices such that every vertex in \(V{\setminus }S\) is reachable by a path of length at most d from one of the vertices in S. When \(d=1\), the set is simply called a dominating set. While the complexity of finding a k-sized dominating set is complete for the complexity class LOGSNP and the parameterized complexity class W[2], it is well-known that every tournament on n vertices has a dominating set of size \(g(n) = \lg n - \lg \lg n + 2\) that can be found in \({{\mathrm{O}}}\left( n^2 \right) \) time. We first show that for any k, one can find a dominating set of size at most \( k + g(n)\) in \({{\mathrm{O}}}\left( n^2/k \right) \) time, and prove an (unconditional) lower bound of \(\varOmega (n^2/k)\) for any \(k > \epsilon \lg n\) for any \(\epsilon >0\). Hence in particular, we can find a \((1+\epsilon ) \lg n\) sized dominating set in the optimal \(\varTheta ({n^2/\lg n})\) time.

For distance-d dominating sets, it is known that any tournament has a distance-2 dominating set consisting of a single vertex. Such a vertex is called a king or a 2-king and can be found in \({{\mathrm{O}}}\left( n \sqrt{n} \right) \) time. It follows that there is a vertex, from which every other vertex is reachable by a path of length at most d for any \(d \ge 2\) and such a vertex is called a d-king. A d-king can be found in \({{\mathrm{O}}}\left( n^{1+1/2^{d-1}} \right) \) for any \(d \ge 2\) [3]. We generalize our result for dominating set to show that for \(d \ge 2\),

• we can find a k-sized distance-d dominating set in a tournament in \({{\mathrm{O}}}\left( k(n/k)^{1+1/2^{d-1}} \right) \) time for any \(k \ge 1\), and
• we can find a \((g(n) + k)\)-sized distance-d dominating set in a tournament using \({{\mathrm{O}}}\left( k(n/k)^{1+1/(2^d-1)} \right) \) time for any \(k \ge 1\).

The second algorithm provides a faster runtime for finding distance-d dominating sets that are larger than g(n). We also show that the second algorithm is optimal whenever \(k \ge \epsilon \lg n\) for any \(\epsilon > 0\).

Thus our algorithms provide tradeoffs between the (additive) approximation factor and the complexity of finding distance-d dominating sets in tournaments. For the problem of finding a d-king, we show some additional results.

Arindam Biswas, Varunkumar Jayapaul, Venkatesh Raman, Srinivasa Rao Satti

On Computational Aspects of Greedy Partitioning of Graphs

Abstract

In this paper we consider a problem of graph \({\mathcal P}\)-coloring consisting in partitioning the vertex set of a graph such that each of the resulting sets induces a graph in a given additive, hereditary class of graphs \({\mathcal P}\). We focus on partitions generated by the greedy algorithm. In particular, we show that given a graph G and an integer k deciding if the greedy algorithm outputs a \({\mathcal P}\)-coloring with a least k colors is \(\mathbb {NP}\)-complete for an infinite number of classes \({\mathcal P}\). On the other hand we get a polynomial-time certifying algorithm if k is fixed and the family of minimal forbidden graphs defining the class \({\mathcal P}\) is finite. We also prove \(\mathrm{co}\mathbb {NP}\)-completeness of the problem of deciding whether for a given graph G the difference between the largest number of colors used by the greedy algorithm and the minimum number of colors required in any \({\mathcal P}\)-coloring of G is bounded by a given constant. A new Brooks-type bound on the largest number of colors used by the greedy \({\mathcal P}\)-coloring algorithm is given.

Piotr Borowiecki

Maximum Edge Bicliques in Tree Convex Bipartite Graphs

Abstract

We show that the computational complexity of the maximum edge biclique (MEB) problem in tree convex bipartite graphs depends on the associated trees. That is, MEB is \(\mathcal {NP}\)-complete for star convex bipartite graphs, but polynomial time solvable for tree convex bipartite graphs whose associated trees have a constant number of leaves. In particular, MEB is polynomial time solvable for triad convex bipartite graphs. Moreover, we show that the same algorithm strategy may not work for circular convex bipartite graphs, and triad convex bipartite graphs are incomparable with respect to chordal bipartite graphs.

Hao Chen, Tian Liu

Complete Submodularity Characterization in the Comparative Independent Cascade Model

Abstract

We study the propagation of comparative ideas in social network. A full characterization for submodularity in the comparative independent cascade (Com-IC) model of two-idea cascade is given, for competing ideas and complementary ideas respectively. We further introduce One-Shot model where agents show less patience toward ideas, and show that in One-Shot model, only the stronger idea spreads with submodularity.

Wei Chen, Hanrui Zhang

A Risk–Reward Model for On-line Financial Leasing Problem with an Interest Rate

Abstract

As an important financing tool, the financial lease can help the lessee obtain the ownership of equipment after paying the rent till the expiration of the lease. Because the lessee does not know the exact length of using the equipment, the financial leasing problem can be viewed as an on-line problem. In this paper, we consider the on-line financial leasing problem with an interest rate where there are two lease options: financial lease and operating lease. We first discuss the traditional deterministic optimal competitive strategy by competitive analysis method. Next, we introduce the risk tolerance and forecast of the decision maker(the lessee) into this problem and acquire the optimal risk–reward strategy. Finally, we give numerical examples and the results show that the introduction of the interest rate and risk tolerance has a significant influence on the deterministic optimal strategy and risk–reward strategy.

Xiaoli Chen, Weijun Xu

Designing and Implementing Algorithms for the Closest String Problem

Abstract

Given a set of n strings of length L and a radius d, the closest string problem (CSP for short) asks for a string \(t_{sol}\) that is within a Hamming distance of d to each of the given strings. It is known that the problem is NP-hard and its optimization version admits a polynomial time approximation scheme (PTAS). A number of parameterized algorithms have been then developed to solve the problem when d is small. Among them, the relatively new ones have not been implemented before and their performance in practice was unknown. In this study, we implement all of them by careful engineering. For those that have been implemented before, our implementation is much faster. For some of those that have not been implemented before, our experimental results show that there exist huge gaps between their theoretical and practical performances. We also design a new parameterized algorithm for the binary case of CSP. The algorithm is deterministic and runs in \(O\left( nL + n^2d\cdot 6.16^d\right) \) time, while the previously best deterministic algorithm runs in \(O\left( nL + nd^3\cdot 6.731^d\right) \) time.

Shota Yuasa, Zhi-Zhong Chen, Bin Ma, Lusheng Wang

The Broken-Triangle Property with Adjoint Values

Abstract

Recently, the Broken Triangle Property (BTP) and its extensions have been proposed to identify hybrid tractable classes of Constraint Satisfaction Problems (CSPs). In this paper, we extend the BTP to the concept of the Broken Triangle Property with adjoint values (BTPv), and then identify a more general hybrid tractable class of binary CSPs. To prove tractability, we present a polynomial-time algorithm to solve CSP instances in the new tractable class using a novel variable selection mechanism, and show correctness of it. We also show that determining whether an instance is in the class can be achieved efficiently. Furthermore, we provide comparisons with the BTP and its extensions showing that as a generalization of the BTP, the BTPv can find novel tractable CSPs, which cannot be identified by those existing tractable classes.

Jian Gao, Rong Chen, Minghao Yin, Hui Li

Online Knapsack Problem Under Concave Functions

Abstract

In this paper, we address an online knapsack problem under concave function f(x), i.e., an item with size x has its profit f(x). We first obtain a simple lower bound \(\max \{q, \frac{f'(0)}{f(1)}\}\), where \(q \approx 1.618\), then show that this bound is not tight, and give an improved lower bound. Finally, we find the online algorithm for linear function [8] can be employed to the concave case, and prove its competitive ratio is \(\frac{f'(0)}{f(1/q)}\), then we give a refined online algorithm with a competitive ratio \(\frac{f'(0)}{f(1)} +1\). And we also give optimal algorithms for some piecewise linear functions.

Xin Han, Ning Ma, Kazuhisa Makino, He Chen

Fluctuated Fitting Under the -metric

Abstract

We consider the problem of fitting a given sequence of integers by an \((\alpha ,\beta )\)-fluctuated one. For a sequence of numbers, those elements which are larger than their direct precursors are called ascends, those elements which are smaller than their direct precursors are called descends. A sequence is said to be \((\alpha ,\beta )\)-fluctuated if there is a descend between any \(\alpha +1\) ascends and an ascend between any \(\beta +1\) descends; or equivalently, if it has at most \(\alpha \) consecutive ascends and at most \(\beta \) consecutive descends, when adjacent equal values are ignored.

Given a sequence of integers \(\mathbf {a}=(a_1,\ldots ,a_n)\) and two parameters \(\alpha ,\beta \) in [1, n], we compute (1) a sequence \(\mathbf {b}=(b_1,\ldots ,b_n)\) of integers that is \((\alpha ,\beta )\)-fluctuated and is closest to \(\mathbf {a}\) among all such sequences; (2) a sequence \(\mathbf {b}'=(b'_1,\ldots ,b'_n)\) of integers that is \((\alpha ,\beta )\)-fluctuated and is bounded by \(\mathbf {a}\) (i.e. \(b'_i\le a_i\) for all i) and is closest to \(\mathbf {a}\) among all such sequences. We measure the distance between sequences under \(\ell _1\) metric.

Our algorithm runs in \(O((\alpha +\beta )\cdot n)\) time, which is linear when \(\alpha ,\beta \) are considered as constants. We also show that a variation of our problem can be solved in the same time complexity. We achieve our result mainly by exploiting and utilizing the property of the closest sequence.

Kai Jin

Optimal Partitioning Which Maximizes the Weighted Sum of Products

Abstract

We consider the problem of partitioning n real numbers to K nonempty groups, so that the weighted sum of products over all groups is maximized. Formally, given \(S=\{r_1,\ldots ,r_n\}\) and \(W=(w_1,\ldots ,w_K)\) where \(w_i\ge 0\), we look for a partition of S into K nonempty groups \(S_1,\ldots ,S_K\), so that \(\sum _{g=1}^{K} (w_g\cdot \prod _{r_j\in S_g}r_j)\) is maximized. Our main result is an \(O(n^2)\) time algorithm for finding an optimal partition.

Kai Jin

Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity

Abstract

Many graph problems such as maximum cut, chromatic number, hamiltonian cycle, and edge dominating set are known to be fixed-parameter tractable (FPT) when parameterized by the treewidth of the input graphs, but become W-hard with respect to the clique-width parameter. Recently, Gajarský et al. proposed a new parameter called modular-width using the notion of modular decomposition of graphs. They showed that the chromatic number problem and the partitioning into paths problem, and hence hamiltonian path and hamiltonian cycle, are FPT when parameterized by this parameter. In this paper, we study modular-width in parameterized parallel complexity and show that the weighted maximum clique problem and the maximum matching problem are fixed-parameter parallel-tractable (FPPT) when parameterized by this parameter.

Faisal N. Abu-Khzam, Shouwei Li, Christine Markarian, Friedhelm Meyer auf der Heide, Pavel Podlipyan

Online Strategies for Evacuating from a Convex Region in the Plane

Abstract

This paper studies an evacuation problem that evacuees inside an affected convex region in the plane try to escape to a boundary of the region as quickly as possible. The boundary information of the region is usually unknown to the evacuees at the beginning during an emergency. But with the help of helicopters or even satellite remote sensing technology, outside rescuers can easily get complete boundary information, and rescuers can share the information with evacuees once getting in touch with the evacuee who firstly reaches a boundary. For the scenario that people evacuate from several different positions, we first show that 3 is a lower bound on the competitive ratio, and present an online strategy with its competitive ratio proved to be no more than \( 2 + \sqrt 5 \). For the scenario that people evacuate from a single initial position, we present a strategy with its competitive ratio very close to the lower bound.

Songhua Li, Yinfeng Xu

A Further Analysis of the Dynamic Dominant Resource Fairness Mechanism

Abstract

Multi-resource fair allocation has been a hot topic in cloud computing. Recently, a dynamic dominant resource fairness mechanism (DDRF) is proposed for dynamic multi-resource fair allocation. In this paper, we develop a linear-time algorithm to find a DDRF solution at each step. Moreover, we give the competitive ratios of the DDRF mechanism under three widely used objectives.

Weidong Li, Xi Liu, Xiaolu Zhang, Xuejie Zhang

A 42k Kernel for the Complementary Maximal Strip Recovery Problem

Abstract

In the Complementary Maximal Strip Recovery problem (CMSR), we are given two strings \(S_1\) and \(S_2\) of distinct letters, where each letter appears either in the positive form or the negative form. The question is whether there are k letters whose deletion results in two matched strings. String \(S_1\) matches string \(S_2\) if there are partitions of \(S_1\) and \(S_2\), such that, for each component \(S_1^i\) of the partition of \(S_1\), there is a unique component \(S_2^j\) in the partition of \(S_2\) which is either equal to \(S_1^i\) or can be obtained from \(S_1^i\) by firstly reversing the order of the letters and then negating the letters. The CMSR problem is known to be NP-hard and fixed-parameter tractable with respect to k. In particular, a linear kernel of size \(74k+4\) was developed based on 8 reduction rules. Very recently, by imposing 3 new reduction rules to the previous kernelization, the linear kernel was improved to 58k. We aim to simplify the kernelization, yet obtain an improved kernel. In particular, we study 7 reduction rules which lead to a linear kernel of size \({42k+24}\).

Wenjun Li, Haiyan Liu, Jianxin Wang, Lingyun Xiang, Yongjie Yang

On-line Scheduling with a Monotonous Subsequence Constraint

Abstract

In this paper, we study a new on-line scheduling problem that each server has to process a monotonous request subsequence. The customer requests are released over-list, and the operator has to decide whether or not to accept the current request and arrange it to a server immediately. The goal of this paper is to find a strategy which accepts the maximal requests. When the number of servers k is less than that of the request types m, we give several lower bounds for this problem. Also, we present the optimal strategy for \( k=1 \) and \( k=2 \) respectively.

Kelin Luo, Yinfeng Xu, Huili Zhang, Wei Luo

A 1.4-Approximation Algorithm for Two-Sided Scaffold Filling

Abstract

Scaffold Filling aims at getting what can be used as whole genomes from scaffolds by computation. Two-Sided Scaffold Filling is given by two scaffolds, asks respectively, to fill one scaffold with those genes in the other but the scaffold itself, so that the two new produced scaffolds have as many as possible common adjacencies. This problem has long been learnt to be NP-Hard and can be approximated to a constant performance ratio. In this paper, we devise an approximation algorithm which can achieve a performance ratio \(1.4 + \varepsilon \). This improves upon the so far best approximation algorithm proposed by Liu et al.

Jingjing Ma, Haitao Jiang, Daming Zhu, Shu Zhang

FPT Algorithms for FVS Parameterized by Split and Cluster Vertex Deletion Sets and Other Parameters

Abstract

A feedback vertex set in an undirected graph is a subset of vertices whose deletion results in an acyclic graph. The problem (which we call FVS) of finding a minimum (or k sized) feedback vertex set is NP-hard in general graphs, while it is polynomial time solvable in some classes of graphs including split graphs and cluster graphs. The current best fixed-parameter tractable (FPT) algorithm for determining whether a given undirected graph has a feedback vertex set of size at most k has a runtime of \({\mathcal O}^*(3.618^k)\)(\({\mathcal O}^*\) notation hides polynomial factors). We consider the parameterized complexity of feedback vertex set parameterized by (vertex deletion) distance to some polynomially solvable classes of graphs including cluster and split graphs. We call a graph G a (c, i)-graph if its vertex set can be partitioned into c cliques and i independent sets. When \(c=0\) and \(i=2\), such a graph is simply a bipartite graph where FVS is NP-hard. It can be deduced easily that FVS is NP-hard even for constant c when \(i \ge 2\). When \(c \le 1\) and \(i \le 1\), then the graph is a split graph where FVS is solvable in polynomial time. Given a graph, let k be the size of the modulator whose deletion results in a (c, i)-graph. We address the parameterized complexity of FVS parameterized by k when \(i \le 1\). Specifically we show that

1.

FVS admits an FPT algorithm that runs in \({\mathcal O}^*(3.148^k)\) time, when \(c \le 1\) and \(i \le 1\) (i.e. when the modulator is a deletion set to a split graph). When \(c \ge 2\), we generalize the algorithm to one with runtime \({\mathcal O}(3.148^{k+c}\cdot n^{{\mathcal O}(c)})\). We also show that FVS is W[1]-hard when parameterized by c (i.e. the c in the exponent of n is unavoidable) if \(i \le 1\) extending a known hardness reduction for the case when \(i=0\).

 

2.

For the special case when \(i=0\) and \(c \ge 1\), and when there are no edges across vertices in different parts (i.e. the modulator is a deletion set to a cluster graph), we give an \({\mathcal O}^*(5^k)\) algorithm.

 

Diptapriyo Majumdar, Venkatesh Raman

A Constant Amortized Time Algorithm for Generating Left-Child Sequences in Lexicographic Order

Abstract

Wu et al. (Theoret. Comput. Sci. 556:25–33, 2014) recently introduced a new type of sequences, called left-child sequences (LC-sequences for short), for representing binary trees. They pointed out that such sequences have a natural interpretation from the view point of data structure and gave a characterization of them. Based on this characterization, Pai et al. (International conference on combinatorial optimization and applications. Springer, Cham, pp. 505–518, 2016) showed that there is an easily implementing algorithm that uses generate-and-test approach to filter all LC-sequences of binary trees with n internal nodes in lexicographic order, while in general this algorithm is not efficient at all. In this paper, we design two novel rotations that allow us to drastically alter the shape of binary trees (and thus their corresponding LC-sequences). As an application, these operations can be employed to generate all LC-sequences in lexicographic order. Accordingly, we present a more efficient algorithm associated with the new types of rotations for generating all LC-sequences and show that it takes only constant amortized running cost.

Kung-Jui Pai, Jou-Ming Chang, Ro-Yu Wu

Geodetic Contraction Games on Trees

Abstract

The geodetic contraction game was introduced by Fraenkel and Harary (Int. J. Game Theor. 18:327–338, 1989). They showed that the problem on trees can be solved by using the algorithm for solving the Hackendot game. However, if we use the algorithm for solving the Hackendot game directly, then it will take \(O(n^3)\) time for solving the geodetic contraction game on trees, where n is the number of vertices in a tree. They also posed the following open question: Is there a more efficient strategy to solve the geodetic contraction game on trees? In this paper, we show that the geodetic contraction game on trees can be solved in \(O(n\log n)\) time.

Yue-Li Wang

On Approximation Algorithms for Two-Stage Scheduling Problems

Abstract

We study scheduling on parallel two-stage flowshops in which each job has to pass through two operations: an R-operation and a T-operation. Motivated by the current research in data centers, we consider two restricted versions of the problem: one restricts that for each job, the R-operation consumes no less time than the T-operation, while the other assumes that the T-operation takes more time than the R-operation for each job. For the first case, we present an online 2-competitive algorithm and an offline 11/6-approximation algorithm. For the second case, we give an online 5/2-competitive algorithm, and prove, for the offline setting, that the problem can be reduced to the problem in the first case.

Guangwei Wu, Jianer Chen, Jianxin Wang

A New Lower Bound for Positive Zero Forcing

Abstract

The positive zero forcing number is a variant of the zero forcing number, which is an important parameter in the study of minimum rank/maximum nullity problems. In this paper, we first introduce the propagation decomposition of graphs; then we use this decomposition to prove a lower bound for the positive zero forcing number of a graph. We apply this lower bound to find the positive zero forcing number of matching-chain graphs. We prove that the positive zero forcing number of a matching-chain graph is equal to its zero forcing number. As a consequence, we prove the conjecture about the positive zero forcing number of the Cartesian product of two paths, and partially prove the conjecture about the positive zero forcing number of the Cartesian product of a cycle and a path. We also show that the positive zero forcing number and the zero forcing number agree for claw-free graphs. We prove that it is NP-complete to find the positive zero forcing number of line graphs.

Boting Yang

Phase Transition for Maximum Not-All-Equal Satisfiability

Abstract

Phase transition is a dramatic transition from one state to another state when a particular parameter varies. This paper aims to study the phase transition of maximum not-all-equal satisfiability problem (Max NAE SAT), an optimization of not-all-equal satisfiability problem (NAE SAT). Given a conjunctive normal formula (CNF) F with n variables and rn k-clauses (the clause exactly contains k literals), we use first-moment method to obtain an upper bound for f(n, rn) the expectation of the maximum number of NAE-satisfied clauses of random Max NAE k-SAT. In addition, we also consider the phase transition of decision version of random Max NAE k-SAT—bounded not-all-equal satisfiability problem (NAE k-SAT(b)). We demonstrate that there is a phase transition point \(r_{k,b}\) separating the region where almost all NAE k-SAT(b) instances can be solved from the region where almost all NAE k-SAT(b) instances can’t be solved. Furthermore, we analyze the upper bound and lower bound for \(r_{k,b}\).

Junping Zhou, Shuli Hu, Tingting Zou, Minghao Yin

Backmatter