Optimal algorithms for the average-constrained maximum-sum segment problem

Given a real number sequence A=(a₁,a₂,…,an), an average lower bound L, and an average upper bound U, the Average-Constrained Maximum-Sum Segment problem is to locate a segment A(i,j)=(ai,ai+1,…,aj) that maximizes _∑i?k?jak subject to . In this paper, we give an O(n)-time algorithm for the case where the average upper bound is ineffective, i.e., U=∞. On the other hand, we prove that the time complexity of the problem with an effective average upper bound is Ω(nlogn) even if the average lower bound is ineffective, i.e., L=−∞.     

Improving loops and vanishing variables in long transportation problems

In this paper the following two results are presented: (1)A method which determines the optimal values of certain variables during the iterative solution process. The closer the current primal feasible solution is to the optimal solution, the greater the number of variables which may be determined. (2) For each current feasible solution (X_ij) of the given m × n transportation problem A, a feasible solution ($\text{X}\text{?}{}_{\mathrm{ij}}$) of an auxiliary m × m(m ?1) transportation problem $\text{A}\text{?}$ is constructed. Problem $\text{A}\text{?}$ is shown to be equivalent to an m(m ? 1) × m(m ? 1) assignment problem with two admissible cells per column. The optimally of (X_ij) is shown to imply the optimality of ($\text{X}\text{?}{}_{\mathrm{ij}}$) and conversely. The best “improving loops” (including the improving loops used in MODI) of $\text{A}\text{?}$ are shown to be the best “improving loops” of A as well.     

Solving the 2-Disjoint Connected Subgraphs Problem Faster than 2 n

The 2-Disjoint Connected Subgraphs problem, given a graph along with two disjoint sets of terminals Z ₁,Z ₂, asks whether it is possible to find disjoint sets A ₁,A ₂, such that Z ₁?A ₁, Z ₂?A ₂ and A ₁,A ₂ induce connected subgraphs. While the naive algorithm runs in O(2 ⁿ n ^O(1)) time, solutions with complexity of form O((2?ε) ⁿ ) have been found only for special graph classes (van ’t Hof et al. in Theor. Comput. Sci. 410(47–49):4834–4843, 2009; Paulusma and van Rooij in Theor. Comput. Sci. 412(48):6761–6769, 2011). In this paper we present an O(1.933 ⁿ ) algorithm for 2-Disjoint Connected Subgraphs in general case, thus breaking the 2 ⁿ barrier. As a counterpoise of this result we show that if we parameterize the problem by the number of non-terminal vertices, it is hard both to speed up the brute-force approach and to find a polynomial kernel.     

An SDP Primal-Dual Algorithm for Approximating the Lovász-Theta Function

The Lovász ?-function (Lovász in IEEE Trans. Inf. Theory, 25:1–7, 1979) of a graph G=(V,E) can be defined as the maximum of the sum of the entries of a positive semidefinite matrix X, whose trace Tr(X) equals 1, and X _ij =0 whenever {i,j}∈E. This function appears as a subroutine for many algorithms for graph problems such as maximum independent set and maximum clique. We apply Arora and Kale’s primal-dual method for SDP to design an algorithm to approximate the ?-function within an additive error of δ>0, which runs in time $O(\frac{\vartheta ^{2} n^{2}}{\delta^{2}} \log n \cdot M_{e})$ , where ?=?(G) and M _e =O(n ³) is the time for a matrix exponentiation operation. It follows that for perfect graphs G, our primal-dual method computes ?(G) exactly in time O(? ² n ⁵logn). Moreover, our techniques generalize to the weighted Lovász ?-function, and both the maximum independent set weight and the maximum clique weight for vertex weighted perfect graphs can be approximated within a factor of (1+?) in time O(? ^?2 n ⁵logn).     

On the cubicity of bipartite graphs

A unit cube in k-dimension (or a k-cube) is defined as the Cartesian product R₁×R₂×?×Rk, where each Ri is a closed interval on the real line of the form [ai,ai+1]. The cubicity of G, denoted as cub(G), is the minimum k such that G is the intersection graph of a collection of k-cubes. Many NP-complete graph problems can be solved efficiently or have good approximation ratios in graphs of low cubicity. In most of these cases the first step is to get a low dimensional cube representation of the given graph.It is known that for a graph G, . Recently it has been shown that for a graph G, cub(G)?4(Δ+1)lnn, where n and Δ are the number of vertices and maximum degree of G, respectively. In this paper, we show that for a bipartite graph G=(A∪B,E) with |A|=n₁, |B|=n₂, n₁?n₂, and Δ^′=min{ΔA,ΔB}, where ΔA=maxa∈Ad(a) and ΔB=maxb∈Bd(b), d(a) and d(b) being the degree of a and b in G, respectively, cub(G)?2(Δ^′+2)⌈lnn₂⌉. We also give an efficient randomized algorithm to construct the cube representation of G in 3(Δ^′+2)⌈lnn₂⌉ dimensions. The reader may note that in general Δ^′ can be much smaller than Δ.     

String matching with inversions and translocations in linear average time (most of the time)

We present an efficient algorithm for finding all approximate occurrences of a given pattern p of length m in a text t of length n allowing for translocations of equal length adjacent factors and inversions of factors. The algorithm is based on an efficient filtering method and has an O(nmmax(α,β))-time complexity in the worst case and O(max(α,β,σ))-space complexity, where α and β are respectively the maximum length of the factors involved in any translocation and inversion, and σ is the alphabet size. Moreover we show that our algorithm has an O(n) average time complexity, whenever , for ε>0. Experiments show that the proposed algorithm achieves very good results in practical cases.     

A fast algorithm for computing a longest common increasing subsequence

Let A=〈a₁,a₂,…,am〉 and B=〈b₁,b₂,…,bn〉 be two sequences, where each pair of elements in the sequences is comparable. A common increasing subsequence of A and B is a subsequence 〈ai₁=bj₁,ai₂=bj₂,…,ail=bjl〉, where i₁<i₂<?<il and j₁<j₂<?<jl, such that for all 1?k<l, we have aik<aik+1. A longest common increasing subsequence of A and B is a common increasing subsequence of the maximum length. This paper presents an algorithm for delivering a longest common increasing subsequence in O(mn) time and O(mn) space.     

Lower bounds for the smallest singular value

Let A = (a_ij) be an n × n complex matrix. Suppose that G(A), the undirected graph of A, has no isolated vertex. Let E be the set of edges of G(A). We prove that the smallest singular value of A, σ_n, satisfies: σ_n ≥ min σ_ij | (i, j) ∈ E, where g_ij ≡ a_i + a_j − [(a_i − a_j)² + (r_i + c_i)(r_j + c_j)]^1/2/2 with a_i ≡ |a_ii| and r_i,c_i are the i^th deleted absolute row sum and column sum of A, respectively. The result simplifies and improves that of Johnson and Szulc: σ_n ≥ min_i≠j σ_ij. (See [1].)     

Efficient Money Burning in General Domains

We study mechanism design where the objective is to maximize the residual surplus, i.e., the total value of the outcome minus the payments charged to the agents, by truthful mechanisms. The motivation comes from applications where the payments charged are not in the form of actual monetary transfers, but take the form of wasted resources. We consider a general mechanism design setting with m discrete outcomes and n multidimensional agents. We present two randomized truthful mechanisms that extract an O(logm) fraction of the maximum social surplus as residual surplus. The first mechanism achieves an O(logm)-approximation to the social surplus, which is improved to an O(1)-approximation by the second mechanism. An interesting feature of the second mechanism is that it optimizes over an appropriately restricted space of probability distributions, thus achieving an efficient tradeoff between social surplus and the total amount of payments charged to the agents.     

List decoding of the first-order binary Reed-Muller codes

A list decoding algorithm is designed for the first-order binary Reed-Muller codes of length n that reconstructs all codewords located within the ball of radius n/2(1 ? ?) about the received vector and has the complexity of O(n ln²(min{? ^?2, n})) binary operations.     

Efficient algorithms for clique problems

The k-clique problem is a cornerstone of NP-completeness and parametrized complexity. When k is a fixed constant, the asymptotically fastest known algorithm for finding a k-clique in an n-node graph runs in O(n0.792k) time (given by Nešet?il and Poljak). However, this algorithm is infamously inapplicable, as it relies on Coppersmith and Winograd's fast matrix multiplication.We present good combinatorial algorithms for solving k-clique problems. These algorithms do not require large constants in their runtime, they can be readily implemented in any reasonable random access model, and are very space-efficient compared to their algebraic counterparts. Our results are the following:

•

We give an algorithm for k-clique that runs in O(nk/(εlogn)^k−1) time and O(nε) space, for all ε>0, on graphs with n nodes. This is the first algorithm to take o(nk) time and O(nc) space for c independent of k.

•

Let k be even. Define a k-semiclique to be a k-node graph G that can be divided into two disjoint subgraphs U={u₁,…,uk/2} and V={v₁,…,vk/2} such that U and V are cliques, and for all i?j, the graph G contains the edge {ui,vj}. We give an time algorithm for determining if a graph has a k-semiclique. This yields an approximation algorithm for k-clique, in the following sense: if a given graph contains a k-clique, then our algorithm returns a subgraph with at least 3/4 of the edges in a k-clique.

     

Sleeping on the Job: Energy-Efficient and Robust Broadcast for Radio Networks

We address the problem of minimizing power consumption when broadcasting a message from one node to all the other nodes in a radio network. To enable power savings for such a problem, we introduce a compelling new data streaming problem which we call the Bad Santa problem. Our results on this problem apply for any situation where: (1) a node can listen to a set of n nodes, out of which at least half are non-faulty and know the correct message; and (2) each of these n nodes sends according to some predetermined schedule which assigns each of them its own unique time slot. In this situation, we show that in order to receive the correct message with probability 1, it is necessary and sufficient for the listening node to listen to a \(\Theta(\sqrt{n})\) expected number of time slots. Moreover, if we allow for repetitions of transmissions so that each sending node sends the message O(log?^? n) times (i.e. in O(log?^? n) rounds each consisting of the n time slots), then listening to O(log?^? n) expected number of time slots suffices. We show that this is near optimal.We describe an application of our result to the popular grid model for a radio network. Each node in the network is located on a point in a two dimensional grid, and whenever a node sends a message m, all awake nodes within L _∞ distance r receive m. In this model, up to \(t<\frac{r}{2}(2r+1)\) nodes within any 2r+1 by 2r+1 square in the grid can suffer Byzantine faults. Moreover, we assume that the nodes that suffer Byzantine faults are chosen and controlled by an adversary that knows everything except for the random bits of each non-faulty node. This type of adversary models worst-case behavior due to malicious attacks on the network; mobile nodes moving around in the network; or static nodes losing power or ceasing to function. Let n=r(2r+1). We show how to solve the broadcast problem in this model with each node sending and receiving an expected \(O(n\log^{2}{|m|}+\sqrt{n}|m|)\) bits where |m| is the number of bits in m, and, after broadcasting a fingerprint of m, each node is awake only an expected \(O(\sqrt{n})\) time slots. Moreover, for t≤(1?ε)(r/2)(2r+1), for any constant ε>0, we can achieve an even better energy savings. In particular, if we allow each node to send O(log?^? n) times, we achieve reliable broadcast with each node sending O(nlog?²|m|+(log?^? n)|m|) bits and receiving an expected O(nlog?²|m|+(log?^? n)|m|) bits and, after broadcasting a fingerprint of m, each node is awake for only an expected O(log?^? n) time slots. Our results compare favorably with previous protocols that required each node to send Θ(|m|) bits, receive Θ(n|m|) bits and be awake for Θ(n) time slots.     

Approximating the Metric TSP in Linear Time

Given a metric graph G=(V,E) of n vertices, i.e., a complete graph with a non-negative real edge cost function satisfying the triangle inequality, the metricity degree of G is defined as \(\beta=\max_{x,y,z\in V}\{\frac{c(x,y)}{c(x,z)+c(y,z)}\}\in[\frac{1}{2},1]\). This value is instrumental to establish the approximability of several NP-hard optimization problems definable on G, like for instance the prominent traveling salesman problem, which asks for finding a Hamiltonian cycle of G of minimum total cost. In fact, this problem can be approximated quite accurately depending on the metricity degree of G, namely by a ratio of either \(\frac{2-\beta}{3(1-\beta)}\) or \(\frac{3\beta^{2}}{3\beta^{2}-2\beta+1}\), for \(\beta<\frac{2}{3}\) or \(\beta\geq \frac{2}{3}\), respectively. Nevertheless, these approximation algorithms have O(n ³) and O(n ^2.5log?^1.5 n) running time, respectively, and therefore they are superlinear in the Θ(n ²) input size. Thus, since many real-world problems are modeled by graphs of huge size, their use might turn out to be unfeasible in practice, and alternative approaches requiring only O(n ²) time are sought. However, with this restriction, all the currently available approaches can only guarantee a 2-approximation ratio for the case β=1, which means a \(\frac{2\beta^{2}}{2\beta^{2}-2\beta+1}\)-approximation ratio for general β<1. In this paper, we show how to elaborate—without affecting the space and time complexity—one of these approaches, namely the classic double-MST heuristic, in order to obtain a 2β-approximate solution. This improvement is effective, since we show that the double-MST heuristic has in general a performance ratio strictly larger than 2β, and we further show that any alternative elaboration of it cannot lead to a performance ratio better than 2β?ε, for any ε>0. Our theoretical results are complemented with an extensive series of experiments, that show the practical appeal of our approach.     

Online vector scheduling and generalized load balancing

We give a polynomial time reduction from the vector scheduling problem (VS) to the generalized load balancing problem (GLB). This reduction gives the first non-trivial online algorithm for VS where vectors come in an online fashion. The online algorithm is very simple in that each vector only needs to minimize the _Lln(md)$L_{ln\left(md\right)}$ norm of the resulting load when it comes, where m$m$ is the number of partitions and d$d$ is the dimension of vectors. It has an approximation bound of elog(md)$elog\left(md\right)$, which is in O(ln(md))$O(ln\left(md\right))$, so it also improves the O(ln²d)$O\left({ln}^{2}d\right)$ bound of the existing polynomial time algorithm for VS. Additionally, the reduction shows that GLB does not have constant approximation algorithms that run in polynomial time unless P=NP$P=NP$.     

The interval-merging problem

A closed interval is an ordered pair of real numbers [x, y], with x ? y. The interval [x, y] represents the set {i ∈ R∣x ? i ? y}. Given a set of closed intervals I={[a₁,b₁],[a₂,b₂],…,[a_k,b_k]}, the Interval-Merging Problem is to find a minimum-cardinality set of intervals M(I)={[x₁,y₁],[x₂,y₂],…,[x_j,y_j]}, j ? k, such that the real numbers represented by equal those represented by . In this paper, we show the problem can be solved in O(d log d) sequential time, and in O(log d) parallel time using O(d) processors on an EREW PRAM, where d is the number of the endpoints of I. Moreover, if the input is given as a set of sorted endpoints, then the problem can be solved in O(d) sequential time, and in O(log d) parallel time using O(d/log d) processors on an EREW PRAM.     

A simplified approach for the design of basically non-interacting multiple-input-multiple-output systems using qft

Quantitative feedback theory (QFT) has presented techniques for the design of multiple-input-multiple-output (MIMO) linear time invariant (LTI) systems with structured parameter uncertainty in the plant P for the satisfaction of specifications on the closed loop transfer function matrix T = [T_ij]. In many practical applications the specifications are of the basically non-interacting (BNIA) type, i.e. a_ii(ω) < | T_ii(jω) | < b_ii(ω), | T_ij(jω) | < b_ij(ω), (i ≠ j) and b_ij(ω) < a_ii(ω) in a significant range of frequencies. In one QFT technique the design is based on expressing when the matrix of compensators G = diag(G_ii(s)), L_i = G_iiQ_ii, P^?1 = [1/Q_ij], D_ij a disturbance due to plant interaction between the different system channels. It is shown in this paper that when the specifications are BNIA and F = diag(F_ii(s)), the effect of the disturbance acting on the main diagonal terms (i.e. D_ii) can be neglected. This observation saves some computational burden because satisfaction of specifications on the T_iis becomes a single-input-single-output (SISO) design problem instead of the more elaborated multiple-input-single-output (MISO) design problem which had to be designed originally. A detailed 2-input-2-output design example is presented illustrating the simpler approach, stressing the importance of considering the correlation between specifications in the design procedure.     

Approximate regular expression pattern matching with concave gap penalties

Given a sequenceA of lengthM and a regular expressionR of lengthP, an approximate regular expression pattern-matching algorithm computes the score of the optimal alignment betweenA and one of the sequencesB exactly matched byR. An alignment between sequencesA=a₁a₂ ... a_M andB=b₁b₂... b_N is a list of ordered pairs, (i₁,j₁), (i₂j₂), ..., (i_t,j_tt) such that i_k < i_k+1 and j_k < j_k+1. In this case the alignmentaligns symbols a_ik and b_jk, and leaves blocks of unaligned symbols, orgaps, between them. A scoring schemeS associates costs for each aligned symbol pair and each gap. The alignment's score is the sum of the associated costs, and an optimal alignment is one of minimal score. There are a variety of schemes for scoring alignments. In a concave gap penalty scoring schemeS={, w}, a function (a, b) gives the score of each aligned pair of symbolsa andb, and aconcave function w(k) gives the score of a gap of lengthk. A function w is concave if and only if it has the property that, for allk > 1, w(k + 1) –w(k) w(k) –w(k –1). In this paper we present an O(MP(logM + log² P)) algorithm for approximate regular expression matching for an arbitrary and any concavew. This work was supported in part by the National Institute of Health under Grant RO1 LM04960.     

An Extended Tree-Width Notion for Directed Graphs Related to the Computation of Permanents

It is well known that permanents of matrices of bounded tree-width are efficiently computable. Here, the tree-width of a square matrix M=(m _ij ) with entries from a field \(\mathbb{K}\) is the tree-width of the underlying graph G _M having an edge (i,j) if and only if the entry m _ij ≠0. Though G _M is directed this does not influence the tree-width definition. Thus, it does not reflect the lacking symmetry when m _ij ≠0 but m _ji =0. The latter however might have impact on the computation of the permanent. In this paper we introduce and study an extended notion of tree-width for directed graphs called triangular tree-width. We give examples where the latter parameter is bounded whereas the former is not. As main result we show that permanents of matrices of bounded triangular tree-width are efficiently computable. This result is shown to hold as well for the Hamiltonian Cycle problem.     

Nearly-Linear Work Parallel SDD Solvers,Low-Diameter Decomposition,and Low-Stretch Subgraphs

We present the design and analysis of a nearly-linear work parallel algorithm for solving symmetric diagonally dominant (SDD) linear systems. On input an SDD n-by-n matrix A with m nonzero entries and a vector b, our algorithm computes a vector \(\tilde{x}\) such that \(\|\tilde{x} - A^{+}b\|_{A} \leq\varepsilon\cdot\|{A^{+}b}\|_{A}\) in \(O(m\log^{O(1)}{n}\log {\frac{1}{\varepsilon}})\) work and \(O(m^{1/3+\theta}\log\frac{1}{\varepsilon})\) depth for any θ>0, where A ⁺ denotes the Moore-Penrose pseudoinverse of A. The algorithm relies on a parallel algorithm for generating low-stretch spanning trees or spanning subgraphs. To this end, we first develop a parallel decomposition algorithm that in O(mlog ^O(1) n) work and polylogarithmic depth, partitions a graph with n nodes and m edges into components with polylogarithmic diameter such that only a small fraction of the original edges are between the components. This can be used to generate low-stretch spanning trees with average stretch O(n ^α ) in O(mlog ^O(1) n) work and O(n ^α ) depth for any α>0. Alternatively, it can be used to generate spanning subgraphs with polylogarithmic average stretch in O(mlog ^O(1) n) work and polylogarithmic depth. We apply this subgraph construction to derive a parallel linear solver. By using this solver in known applications, our results imply improved parallel randomized algorithms for several problems, including single-source shortest paths, maximum flow, minimum-cost flow, and approximate maximum flow.