ALBERT

Description: There is excitement within the algorithms community about a new partitioning method introduced by Yaroslavskiy. This algorithm renders Quicksort slightly faster than the case when it runs under classic partitioning methods. We show that this improved performance in Quicksort is not sustained in Quickselect; a variant of Quicksort for finding order statistics. We investigate the number of comparisons made by Quickselect to find a key with a randomly selected rank under Yaroslavskiy’s algorithm. This grand averaging is a smoothing operator over all individual distributions for specific fixed order statistics. We give the exact grand average. The grand distribution of the number of comparison (when suitably scaled) is given as the fixed-point solution of a distributional equation of a contraction in the Zolotarev metric space. Our investigation shows that Quickselect under older partitioning methods slightly outperforms Quickselect under Yaroslavskiy’s algorithm, for an order statistic of a random rank. Similar results are obtained for extremal order statistics, where again we find the exact average, and the distribution for the number of comparisons (when suitably scaled). Both limiting distributions are of perpetuities (a sum of products of independent mixed continuous random variables).

Description: We study an online version of linear Fisher market. In this market there are \(m\) buyers and a set of \(n\) dividable goods to be allocated to the buyers. The utility that buyer \(i\) derives from good \(j\) is \(u_{ij}\) . Given an allocation \(\hat{U}\) in which buyer \(i\) has utility \(\hat{U}_i\) we study a quality measure that is based on taking an average of the ratios \(U_{i}/\hat{U}_i\) with respect to any other allocation \(U\) . Market equilibrium allocation is the optimal solution with respect to this measure. Our setting is online and so the allocation of each good should be done without any knowledge of the upcoming goods. We design an online algorithm for the problem that is only worse by a logarithmic factor than any other solution with respect to this quality measure, and in particular competes with the market equilibrium allocation. We prove a tight lower bound which shows that our algorithm is optimal up to constants. Our algorithm uses a primal dual convex programming scheme. To the best of our knowledge this is the first time that such a scheme is used in the online framework.

Description: The order- \(k\) Voronoi diagram of line segments has properties surprisingly different from its counterpart for points. For example, a single order- \(k\) Voronoi region may consist of \(\varOmega (n)\) disjoint faces. In this paper, we analyze the structural properties of this diagram and show that its combinatorial complexity is \(O(k(n-k))\) , for \(n\) non-crossing line segments, despite the presence of disconnected regions. The same bound holds for \(n\) intersecting line segments, for \(k\ge n/2\) . We also consider the order- \(k\) Voronoi diagram of line segments that form a planar straight-line graph, and augment the definition of an order- \(k\) diagram to cover sites that are not disjoint. On the algorithmic side, we extend the iterative approach to construct this diagram, handling complications caused by the presence of disconnected regions. All bounds are valid in the general \(L_p\) metric, \(1\le p\le \infty \) . For non-crossing segments in the \(L_\infty \) and \(L_1\) metrics, we show a tighter \(O((n-k)^2)\) bound for \(k〉n/2\) .

Description: We study three complexity parameters that, for each vertex v , are an upper bound for the number of cliques that are sufficient to cover a subset S ( v ) of its neighbors. We call a graph k-perfectly groupable if S ( v ) consists of all neighbors, k-simplicial if S ( v ) consists of the neighbors with a higher number after assigning distinct numbers to all vertices, and k-perfectly orientable if S ( v ) consists of the endpoints of all outgoing edges from v for an orientation of all edges. These parameters measure in some sense how chordal-like a graph is—the last parameter was not previously considered in literature. The similarity to chordal graphs is used to construct simple polynomial-time approximation algorithms with constant approximation ratio for many NP-hard problems, when restricted to graphs for which at least one of the three complexity parameters is bounded by a constant. As applications we present approximation algorithms with constant approximation ratio for maximum weighted independent set, minimum (independent) dominating set, minimum vertex coloring, maximum weighted clique, and minimum clique partition for large classes of intersection graphs.

Description: We present a data structure for maintaining the geodesic hull of a set of points ( site s) in the presence of pairwise noncrossing line segments ( barrier s) that subdivide a bounding box into simply connected faces. For m barriers and n sites, our data structure has O (( m + n )log n ) size. It supports a mixed sequence of O ( m ) barrier insertions and O ( n ) site deletions in $O((m+n) \operatorname{polylog}(mn))$ total time, and answers analogues of standard convex hull queries in $O(\operatorname{polylog}(mn))$ time. Our data structure supports a generalization of the sweep line technique, in which the sweep wavefront is a simple closed polygonal curve, and it sweeps a set of n points in the plane by simple moves . We reduce the total time of supporting m online moves of a polygonal wavefront sweep algorithm from the naïve $O(m\sqrt{n} \operatorname{polylog}n)$ to $O((m+n) \operatorname{polylog}(mn))$ .

Description: We investigate the computational complexity of the empire colouring problem (as defined by Percy Heawood in Q. J. Pure Appl. Math. 24:332–338, 1890 ) for maps containing empires formed by exactly r 〉1 countries each. We prove that the problem can be solved in polynomial time using s colours on maps whose underlying adjacency graph has no induced subgraph of average degree larger than s / r . However, if s ≥3, the problem is NP-hard even if the graph is a for forests of paths of arbitrary lengths (for any r ≥2, provided $s 〈 2r - \sqrt{2r + \frac{1}{4}}+ \frac{3}{2}$ ). Furthermore we obtain a complete characterization of the problem’s complexity for the case when the input graph is a tree, whereas our result for arbitrary planar graphs fall just short of a similar dichotomy. Specifically, we prove that the empire colouring problem is NP-hard for trees, for any r ≥2, if 3≤ s ≤2 r −1 (and polynomial time solvable otherwise). For arbitrary planar graphs we prove NP-hardness if s 〈7 for r =2, and s 〈6 r −3, for r ≥3. The result for planar graphs also proves the NP-hardness of colouring with less than 7 colours graphs of thickness two and less than 6 r −3 colours graphs of thickness r ≥3.

Description: Inspired by the CONFIDANT protocol (Buchegger and Boudec in Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking & Computing, pp. 226–236, 2002), we define and study a basic reputation-based protocol in multihop wireless networks with selfish nodes. Its reputation mechanism is implemented through the ability of any node to define a threshold of tolerance for any of its neighbors, and to cut the connection to any of these neighbors that refuse to forward an amount of flow above that threshold. The main question we would like to address is whether one can set the initial conditions so that the system reaches an equilibrium state where a non-zero amount of every commodity is routed. This is important in emergency situations, where all nodes need to be able to communicate even with a small bandwidth. Following a standard approach, we model this protocol as a game, and we give necessary and sufficient conditions for the existence of non-trivial Nash equilibria. Then we enhance these conditions with extra conditions that give a set of necessary and sufficient conditions for the existence of connected Nash equilibria. We note that it is not always necessary for all the flow originating at a node to reach its destination at equilibrium. For example, a node may be using unsuccessful flow in order to effect changes in a distant part of the network that will prove quite beneficial to it. We show that we can decide in polynomial time whether there exists a (connected) equilibrium without unsuccessful flows. In that case we calculate (in polynomial time) initial values that impose such an equilibrium on the network. On the negative side, we prove that it is NP-hard to decide whether a connected equilibrium exists in general (i.e., with some nodes using unsuccessful flows at equilibrium).

Description: In this paper we investigate dynamic speed scaling, a technique to reduce energy consumption in variable-speed microprocessors. While prior research has focused mostly on single processor environments, in this paper we investigate multiprocessor settings. We study the basic problem of scheduling a set of jobs, each specified by a release date, a deadline and a processing volume, on variable-speed processors so as to minimize the total energy consumption. We first settle the problem complexity if unit size jobs have to be scheduled. More specifically, we devise a polynomial time algorithm for jobs with agreeable deadlines and prove NP-hardness results if jobs have arbitrary deadlines. For the latter setting we also develop a polynomial time algorithm achieving a constant factor approximation guarantee. Additionally, we study problem settings where jobs have arbitrary processing requirements and, again, develop constant factor approximation algorithms. We finally transform our offline algorithms into constant competitive online strategies.

Description: We consider the online metric matching problem in which we are given a metric space, k of whose points are designated as servers. Over time, up to k requests arrive at an arbitrary subset of points in the metric space, and each request must be matched to a server immediately upon arrival, subject to the constraint that at most one request is matched to any particular server. Matching decisions are irrevocable and the goal is to minimize the sum of distances between the requests and their matched servers. We give an O (log 2 k )-competitive randomized algorithm for the online metric matching problem. This improves upon the best known guarantee of O (log 3 k ) on the competitive factor due to Meyerson, Nanavati and Poplawski (SODA ’06, pp. 954–959, 2006 ). It is known that for this problem no deterministic algorithm can have a competitive better than 2 k −1, and that no randomized algorithm can have a competitive ratio better than ln k .

Description: Geometric routing by using virtual locations is an elegant way for solving network routing problems. In its simplest form, greedy routing, a message is simply forwarded to a neighbor that is closer to the destination. It has been an open conjecture whether every 3-connected plane graph has a greedy drawing in the Euclidean plane R 2 (by Papadimitriou and Ratajczak in Theor. Comp. Sci. 344(1):3–14, 2005 ). Leighton and Moitra (Discrete Comput. Geom. 44(3):686–705, 2010 ) recently settled this conjecture positively. One main drawback of this approach is that the coordinates of the virtual locations require Ω ( n log n ) bits to represent (the same space usage as traditional routing table approaches). This makes greedy routing infeasible in applications. In this paper, we show that the classical Schnyder drawing in R 2 of plane triangulations is greedy with respect to a simple natural metric function H ( u , v ) over R 2 that is equivalent to Euclidean metric D E ( u , v ) (in the sense that $D_{E}(u,v) \leq H(u,v) \leq2\sqrt{2}D_{E}(u,v)$ ). The drawing uses two integer coordinates between 0 and 2 n −5, which can be represented by log n bits. We also show that the classical Schnyder drawing in R 2 of 3-connected plane graphs is weakly greedy with respect to the same metric function H (∗,∗). The drawing uses two integer coordinates between 0 and  f (where f is the number of internal faces of G ).

Description: In the online packet buffering problem (also known as the unweighted FIFO variant of buffer management), we focus on a single network packet switching device with several input ports and one output port. This device forwards unit-size, unit-value packets from input ports to the output port. Buffers attached to input ports may accumulate incoming packets for later transmission; if they cannot accommodate all incoming packets, their excess is lost. A packet buffering algorithm has to choose from which buffers to transmit packets in order to minimize the number of lost packets and thus maximize the throughput. We present a tight lower bound of e/(e−1)≈1.582 on the competitive ratio of the throughput maximization, which holds even for fractional or randomized algorithms. This improves the previously best known lower bound of 1.4659 and matches the performance of the algorithm Random Schedule . Our result contradicts the claimed performance of the algorithm Random Permutation ; we point out a flaw in its original analysis.

Description: Suffix trees and suffix arrays are two of the most widely used data structures for text indexing. Each uses linear space and can be constructed in linear time for polynomially sized alphabets. However, when it comes to answering queries with worst-case deterministic time bounds, the prior does so in O ( m log| Σ |) time, where m is the query size, | Σ | is the alphabet size, and the latter does so in O ( m +log n ) time, where n is the text size. If one wants to output all appearances of the query, an additive cost of O ( occ ) time is sufficient, where occ is the size of the output. Notice that it is possible to obtain a worst case, deterministic query time of O ( m ) but at the cost of super-linear construction time or space usage. We propose a novel way of combining the two into, what we call, a suffix tray . The space and construction time remain linear and the query time improves to O ( m +log| Σ |) for integer alphabets from a linear range, i.e. Σ ⊂{1,…, cn }, for an arbitrary constant c . The construction and query are deterministic. Here also an additive O ( occ ) time is sufficient if one desires to output all appearances of the query. We also consider the online version of indexing, where the text arrives online, one character at a time, and indexing queries are answered in tandem. In this variant we create a cross between a suffix tree and a suffix list (a dynamic variant of suffix array) to be called a suffix trist ; it supports queries in O ( m +log| Σ |) time. The suffix trist also uses linear space. Furthermore, if there exists an online construction for a linear-space suffix tree such that the cost of adding a character is worst-case deterministic f ( n ,| Σ |) ( n is the size of the current text), then one can further update the suffix trist in O ( f ( n ,| Σ |)+log| Σ |) time. The best currently known worst-case deterministic bound for f ( n ,| Σ |) is O (log n ) time.

Description: We introduce a new variant of the geometric Steiner arborescence problem, motivated by the layout of flow maps. Flow maps show the movement of objects between places. They reduce visual clutter by bundling curves smoothly and avoiding self-intersections. To capture these properties, our angle-restricted Steiner arborescences , or flux trees , connect several targets to a source with a tree of minimal length whose arcs obey a certain restriction on the angle they form with the source. We study the properties of optimal flux trees and show that they are crossing-free and consist of logarithmic spirals and straight lines. Flux trees have the shallow-light property . We show that computing optimal flux trees is NP-hard. Hence we consider a variant of flux trees which uses only logarithmic spirals. Spiral trees approximate flux trees within a factor depending on the angle restriction. Computing optimal spiral trees remains NP-hard, but we present an efficient 2-approximation, which can be extended to avoid “positive monotone” obstacles.

Description: We study the problem of finding small s – t separators that induce graphs having certain properties. It is known that finding a minimum clique s – t separator is polynomial-time solvable (Tarjan in Discrete Math. 55:221–232, 1985 ), while for example the problems of finding a minimum s – t separator that induces a connected graph or forms an independent set are fixed-parameter tractable when parameterized by the size of the separator (Marx et al. in ACM Trans. Algorithms 9(4): 30, 2013 ). Motivated by these results, we study properties that generalize cliques, independent sets, and connected graphs, and determine the complexity of finding separators satisfying these properties. We investigate these problems also on bounded-degree graphs. Our results are as follows: Finding a minimum c -connected s – t separator is FPT for c =2 and W [1]-hard for any c ≥3. Finding a minimum s – t separator with diameter at most d is W [1]-hard for any d ≥2. Finding a minimum r -regular s – t separator is W [1]-hard for any r ≥1. For any decidable graph property, finding a minimum s – t separator with this property is FPT parameterized jointly by the size of the separator and the maximum degree. Finding a connected s – t separator of minimum size does not have a polynomial kernel, even when restricted to graphs of maximum degree at most 3, unless $\mathrm{NP} \subseteq \mathrm{coNP/poly}$ . In order to prove (1), we show that the natural c -connected generalization of the well-known Steiner Tree problem is FPT for c =2 and W [1]-hard for any c ≥3.

Description: Consider laying out a fixed-topology binary tree of N nodes into external memory with block size B so as to minimize the worst-case number of block memory transfers required to traverse a path from the root to a node of depth  D . We prove that the optimal number of memory transfers is $$\begin{aligned} \begin{cases} \varTheta( {D \over\lg(1{+}B)} ) & \mathrm{when}~D = O(\lg N), \\ \varTheta( {\lg N \over\lg(1{+}{B \lg N \over D} )} ) & \mathrm{when}~D = \varOmega(\lg N)~\mathrm{and}~D = O(B \lg N), \\ \varTheta( {D \over B} ) & \mathrm{when}~D = \varOmega(B \lg N). \end{cases} \end{aligned}$$

Description: We consider rumor spreading on random graphs and hypercubes in the quasirandom phone call model. In this model, every node has a list of neighbors whose order is specified by an adversary. In step i every node opens a channel to its i th neighbor (modulo degree) on that list, beginning from a randomly chosen starting position. Then, the channels can be used for bi-directional communication in that step. The goal is to spread a message efficiently to all nodes of the graph. For random graphs (with sufficiently many edges) we present an address-oblivious algorithm with runtime O (log n ) that uses at most O ( n loglog n ) message transmissions. For hypercubes of dimension log n we present an address-oblivious algorithm with runtime O (log n ) that uses at most O ( n (loglog n ) 2 ) message transmissions. Together with a result of Elsässer (Proc. of SPAA’06, pp. 148–157, 2006 ), our results imply that for random graphs the communication complexity of the quasirandom phone call model is significantly smaller than that of the standard phone call model.

Description: Let ε 1 , ε 2 be two non negative numbers. An approximate rectangle of influence drawing (also called ( ε 1 , ε 2 )-RID) is a proximity drawing of a graph such that: (i) if u , v are adjacent vertices then their rectangle of influence “scaled down” by the factor $\frac{1}{1+\varepsilon_{1}}$ does not contain other vertices of the drawing; (ii) if u , v are not adjacent, then their rectangle of influence “blown-up” by the factor 1+ ε 2 contains some vertices of the drawing other than u and v . Firstly, we prove that all planar graphs have an ( ε 1 , ε 2 )-RID for any ε 1 〉0 and ε 2 〉0, while there exist planar graphs which do not admit an ( ε 1 ,0)-RID and planar graphs which do not admit a (0, ε 2 )-RID. Then, we investigate (0, ε 2 )-RIDs; we prove that both the outerplanar graphs and a suitably defined family of graphs without separating 3-cycles admit this type of drawing. Finally, we study polynomial area approximate rectangle of influence drawings and prove that (0, ε 2 )-RIDs of proper track planar graphs (a superclass of the outerplanar graphs) can be computed in polynomial area for any ε 2 〉2. As for values of ε 2 such that ε 2 ≤2, we describe a drawing algorithm that computes (0, ε 2 )-RIDs of binary trees in area $O(n^{c + f(\varepsilon_{2})})$ , where c is a positive constant, f ( ε 2 ) is a poly-logarithmic function that tends to infinity as ε 2 tends to zero, and n is the number of vertices of the input tree.

Description: Given an n -node, undirected and 2-edge-connected graph G =( V , E ) with positive real weights on its m edges, given a set of k source nodes S ⊆ V , and given a spanning tree T of G , the routing cost from S of T is the sum of the distances in T from every source s ∈ S to all the other nodes of G . If an edge e of T undergoes a transient failure, and one needs to promptly reestablish the connectivity, then to reduce set-up and rerouting costs it makes sense to temporarily replace e by means of a swap edge , i.e., an edge in G reconnecting the two subtrees of T induced by the removal of e . Then, a best swap edge for e is a swap edge which minimizes the routing cost from S of the tree obtained after the swapping. As a natural extension, the all-best swap edges problem is that of finding a best swap edge for every edge of T , and this has been recently solved in O ( mn ) time and linear space. In this paper, we focus our attention on the relevant cases in which k = O (1) and k = n , which model realistic communication paradigms. For these cases, we improve the above result by presenting an $\widetilde{O}(m)$ time and linear space algorithm. Moreover, for the case k = n , we also provide an accurate analysis showing that the obtained swap tree is effective in terms of routing cost. Indeed, if the input tree T has a routing cost from V which is a constant-factor away from that of a minimum routing-cost spanning tree (whose computation is a problem known to be in APX ), and if in addition nodes in T enjoys a suitable distance stretching property from a tree centroid (which can be constructively induced, as we show), then the tree obtained after the swapping has a routing cost from V which is still a constant-ratio approximation of that of a new (i.e., in the graph deprived of the failed edge) minimum routing-cost spanning tree.

Description: In the Parameterized Connected Dominating Set problem the input consists of a graph G and a positive integer k , and the question is whether there is a set S of at most k vertices in  G —a  connected dominating set of G —such that (i)  S is a dominating set of G , and (ii) the subgraph G [ S ] induced by S is connected; the parameter is k . The underlying decision problem is a basic connectivity problem which is long known to be NP-complete, and it has been extensively studied using several algorithmic approaches. Parameterized Connected Dominating Set is W[2]-hard, and therefore it is unlikely (Downey and Fellows, Parameterized Complexity, Springer, 1999 ) that the problem has fixed-parameter tractable (FPT) algorithms or polynomial kernels in graphs in general. We investigate the effect of excluding short cycles, as subgraphs, on the kernelization complexity of Parameterized Connected Dominating Set . The girth of a graph G is the length of a shortest cycle in G . It turns out that the Parameterized Connected Dominating Set problem is hard on graphs with small cycles, and becomes progressively easier as the girth increases. More precisely, we obtain the following kernelization landscape: Parameterized Connected Dominating Set does not have a kernel of any size on graphs of girth three or four (since the problem is W[2]-hard); admits a kernel of size 2 k k 3 k on graphs of girth at least five; has no polynomial kernel (unless the Polynomial Hierarchy collapses to the third level) on graphs of girth at most six, and, has a cubic ( $\mathcal {O}(k^{3})$ ) vertex kernel on graphs of girth at least seven. While there is a large and growing collection of parameterized complexity results available for problems on graph classes characterized by excluded minors , our results add to the very few known in the field for graph classes characterized by excluded subgraphs .

Description: Cops and robber games , introduced by Winkler and Nowakowski (in Discrete Math. 43(2–3), 235–239, 1983 ) and independently defined by Quilliot (in J. Comb. Theory, Ser. B 38(1), 89–92, 1985 ), concern a team of cops that must capture a robber moving in a graph. We consider the class of k -chordal graphs, i.e., graphs with no induced (chordless) cycle of length greater than k , k ≥3. We prove that k −1 cops are always sufficient to capture a robber in k -chordal graphs. This leads us to our main result, a new structural decomposition for a graph class including k -chordal graphs. We present a polynomial-time algorithm that, given a graph G and k ≥3, either returns an induced cycle larger than k in G , or computes a tree-decomposition of G , each bag of which contains a dominating path with at most k −1 vertices. This allows us to prove that any k -chordal graph with maximum degree Δ has treewidth at most ( k −1)( Δ −1)+2, improving the O ( Δ ( Δ −1) k −3 ) bound of Bodlaender and Thilikos (Discrete Appl. Math. 79(1–3), 45–61, 1997 . Moreover, any graph admitting such a tree-decomposition has small hyperbolicity). As an application, for any n -vertex graph admitting such a tree-decomposition, we propose a compact routing scheme using routing tables, addresses and headers of size O ( k log Δ +log n ) bits and achieving an additive stretch of O ( k log Δ ). As far as we know, this is the first routing scheme with O ( k log Δ +log n )-routing tables and small additive stretch for k -chordal graphs.

Description: We study the boundary of tractability for the Max-Cut problem in graphs. Our main result shows that Max-Cut parameterized above the Edwards-Erdős bound is fixed-parameter tractable: we give an algorithm that for any connected graph with n vertices and m edges finds a cut of size $$ \frac{m}{2} + \frac{n-1}{4} + k $$ in time 2 O ( k ) ⋅ n 4 , or decides that no such cut exists. This answers a long-standing open question from parameterized complexity that has been posed a number of times over the past 15 years. Our algorithm has asymptotically optimal running time, under the Exponential Time Hypothesis, and is strengthened by a polynomial-time computable kernel of polynomial size.

Description: We consider so-called “incremental” dynamic programming algorithms, and are interested in the number of subproblems produced by them. The classical dynamic programming algorithm for the Knapsack problem is incremental, produces nK subproblems and nK 2 relations (wires) between the subproblems, where n is the number of items, and K is the knapsack capacity. We show that any incremental algorithm for this problem must produce about nK subproblems, and that about nK log K wires (relations between subproblems) are necessary. This holds even for the Subset-Sum problem. We also give upper and lower bounds on the number of subproblems needed to approximate the Knapsack problem. Finally, we show that the Maximum Bipartite Matching problem and the Traveling Salesman problem require exponential number of subproblems. The goal of this paper is to leverage ideas and results of boolean circuit complexity for proving lower bounds on dynamic programming.

Description: In this paper we provide improved approximation algorithms for the Min-Max Tree Cover and Bounded Tree Cover problems. Given a graph G =( V , E ) with weights w : E →ℤ + , a set T 1 , T 2 ,…, T k of subtrees of G is called a tree cover of G if $V=\bigcup_{i=1}^{k} V(T_{i})$ . In the Min-Max k -tree Cover problem we are given graph G and a positive integer k and the goal is to find a tree cover with k trees, such that the weight of the largest tree in the cover is minimized. We present a 3-approximation algorithm for this improving the two different approximation algorithms presented in Arkin et al. (J. Algorithms 59:1–18, 2006 ) and Even et al. (Oper. Res. Lett. 32(4):309–315, 2004 ) with ratio 4. The problem is known to have an APX-hardness lower bound of $\frac{3}{2}$ (Xu and Wen in Oper. Res. Lett. 38:169–173, 2010 ). In the Bounded Tree Cover problem we are given graph G and a bound λ and the goal is to find a tree cover with minimum number of trees such that each tree has weight at most λ . We present a 2.5-approximation algorithm for this, improving the 3-approximation bound in Arkin et al. (J. Algorithms 59:1–18, 2006 ).

Description: A set of identical, mobile agents is deployed in a weighted network. Each agent has a battery—a power source allowing it to move along network edges. An agent uses its battery proportionally to the distance traveled. We consider two tasks: convergecast , in which at the beginning, each agent has some initial piece of information, and information of all agents has to be collected by some agent; and broadcast in which information of one specified agent has to be made available to all other agents. In both tasks, the agents exchange the currently possessed information when they meet. The objective of this paper is to investigate what is the minimal value of power, initially available to all agents, so that convergecast or broadcast can be achieved. We study this question in the centralized and the distributed settings. In the centralized setting, there is a central monitor that schedules the moves of all agents. In the distributed setting every agent has to perform an algorithm being unaware of the network. In the centralized setting, we give a linear-time algorithm to compute the optimal battery power and the strategy using it, both for convergecast and for broadcast, when agents are on the line. We also show that finding the optimal battery power for convergecast or for broadcast is NP-hard for the class of trees. On the other hand, we give a polynomial algorithm that finds a 2-approximation for convergecast and a 4-approximation for broadcast, for arbitrary graphs.In the distributed setting, we give a 2-competitive algorithm for convergecast in trees and a 4-competitive algorithm for broadcast in trees. The competitive ratio of 2 is proved to be the best for the problem of convergecast, even if we only consider line networks. Indeed, we show that there is no ( \(2-\epsilon \) )-competitive algorithm for convergecast or for broadcast in the class of lines, for any \(\epsilon 〉0\) .

Description: The \(3\) -coloring problem is well known to be NP-complete. It is also well known that it remains NP-complete when the input is restricted to graphs with diameter  \(4\) . Moreover, assuming the Exponential Time Hypothesis (ETH), \(3\) -coloring cannot be solved in time \(2^{o(n)}\) on graphs with  \(n\) vertices and diameter at most  \(4\) . In spite of extensive studies of the \(3\) -coloring problem with respect to several basic parameters, the complexity status of this problem on graphs with small diameter, i.e. with diameter at most  \(2\) , or at most  \(3\) , has been an open problem. In this paper we investigate graphs with small diameter. For graphs with diameter at most  \(2\) , we provide the first subexponential algorithm for \(3\) -coloring, with complexity \(2^{O(\sqrt{n\log n})}\) . Furthermore we extend the notion of an articulation vertex to that of an articulation neighborhood , and we provide a polynomial algorithm for \(3\) -coloring on graphs with diameter  \(2\) that have at least one articulation neighborhood. For graphs with diameter at most  \(3\) , we establish the complexity of \(3\) -coloring by proving for every  \({\varepsilon \in [0,1)}\) that \(3\) -coloring is NP-complete on triangle-free graphs of diameter  \(3\) and radius \(2\) with \(n\) vertices and minimum degree \(\delta =\varTheta (n^{\varepsilon })\) . Moreover, assuming ETH, we use three different amplification techniques of our hardness results, in order to obtain for every  \({\varepsilon \in [0,1)}\) subexponential asymptotic lower bounds for the complexity of \(3\) -coloring on triangle-free graphs with diameter  \(3\) and minimum degree  \({\delta =\varTheta (n^{\varepsilon })}\) . Finally, we provide a \(3\) -coloring algorithm with running time  \({ 2^{O\left( \min \{\delta \varDelta ,\ \frac{n}{\delta }\log \delta \}\right) }}\) for arbitrary graphs with diameter  \(3\) , where \(n\) is the number of vertices and \( \delta \) (resp.  \(\varDelta \) ) is the minimum (resp. maximum) degree of the input graph. To the best of our knowledge, this is the first subexponential algorithm for graphs with \({\delta =\omega (1)}\) and for graphs with \({\delta =O(1)}\) and \(\varDelta =o(n)\) . Due to the above lower bounds of the complexity of \(3\) -coloring, the running time of this algorithm is asymptotically almost tight when the minimum degree of the input graph is \(\delta =\varTheta (n^{\varepsilon })\) , where \({\varepsilon \in [\frac{1}{2},1)}\) , as its time complexity is \({2^{O\left( \frac{n}{\delta } \log \delta \right) } = 2^{O\left( n^{1-\varepsilon } \log n\right) }}\) and the corresponding lower bound states that there is no \(2^{o\left( n^{1-\varepsilon }\right) }\) -time algorithm.

Description: In the Test Cover problem we are given a hypergraph \(H=(V, {\mathcal {E}})\) with \(|V|=n, |{\mathcal {E}}|=m\) , and we assume that \({\mathcal {E}}\) is a test cover , i.e. for every pair of vertices \(x_i, x_j\) , there exists an edge \(e \in {\mathcal {E}}\) such that \(|\{x_i,x_j\}\cap e|=1\) . The objective is to find a minimum subset of \({\mathcal {E}}\) which is a test cover. The problem is used for identification across many areas, and is NP-complete. From a parameterized complexity standpoint, many natural parameterizations of Test Cover are either \(W[1]\) -complete or have no polynomial kernel unless \(coNP\subseteq NP/poly\) , and thus are unlikely to be solveable efficiently. However, in practice the size of the edges is often bounded. In this paper we study the parameterized complexity of Test - \(r\) - Cover , the restriction of Test Cover in which each edge contains at most \(r \ge 2\) vertices. In contrast to the unbounded case, we show that the following below-bound parameterizations of Test - \(r\) - Cover are fixed-parameter tractable with a polynomial kernel: (1) Decide whether there exists a test cover of size \(n-k\) , and (2) decide whether there exists a test cover of size \(m-k\) , where \(k\) is the parameter. In addition, we prove a new lower bound \(\lceil \frac{2(n-1)}{r+1} \rceil \) on the minimum size of a test cover when the size of each edge is bounded by \(r\) . Test - \(r\) - Cover parameterized above this bound is unlikely to be fixed-parameter tractable; in fact, we show that it is para-NP-complete, as it is NP-hard to decide whether an instance of Test - \(r\) - Cover has a test cover of size exactly \(\frac{2(n-1)}{r+1}\) .

Description: We revisit the problem of finding \(k\) paths with a minimum number of shared edges between two vertices of a graph. An edge is called shared if it is used in more than one of the \(k\) paths. We provide a \({\lfloor {k/2}\rfloor }\) -approximation algorithm for this problem, improving the best previous approximation factor of \(k-1\) . We also provide the first approximation algorithm for the problem with a sublinear approximation factor of \(O(n^{3/4})\) , where \(n\) is the number of vertices in the input graph. For sparse graphs, such as bounded-degree and planar graphs, we show that the approximation factor of our algorithm can be improved to \(O(\sqrt{n})\) . While the problem is NP-hard, and even hard to approximate to within an \(O(\log n)\) factor, we show that the problem is polynomially solvable when \(k\) is a constant. This settles an open problem posed by Omran et al. regarding the complexity of the problem for small values of \(k\) . We present most of our results in a more general form where each edge of the graph has a sharing cost and a sharing capacity, and there is a vulnerability parameter \(r\) that determines the number of times an edge can be used among different paths before it is counted as a shared/vulnerable edge.

Description: We give an approximation algorithm for fractional packing and covering linear programs (linear programs with non-negative coefficients). Given a constraint matrix with n non-zeros, r rows, and c columns, the algorithm (with high probability) computes feasible primal and dual solutions whose costs are within a factor of 1+ ε of opt (the optimal cost) in time O (( r + c )log( n )/ ε 2 + n ).

Description: The undirected negative cost cycle detection (UNCCD) problem is concerned with checking whether an undirected, weighted graph contains a negative cost cycle . Known approaches for solving this problem involve reducing it to either the minimum weight \(b\) - matching problem or the minimum weight \(T\) - join problem . In this paper, we formally describe these two approaches and provide the tightest known analysis of the \(b\) -matching approach. Our analysis establishes that the \(b\) -matching approach runs in \(O((n+m)^{2}\cdot \log (n+m))\) time on a graph with \(n\) nodes and \(m\) edges. We also explore the case where the edge costs are integers in the range \(\{-K,\ldots , K\}\) . For \(K = O(1)\) , we provide improved time bounds for both the above-mentioned approaches by exploiting the existence of specialized procedures for optimization problems in graphs with integral positive edge costs. We show that while the \(T\) -join algorithm has a better time bound for general graphs, the \(b\) -matching algorithm is more efficient for sparse graphs. Finally, we present one of the first , extensive empirical studies for the UNCCD problem. We examine both approaches on several different families of undirected graphs. Our findings provide insight into the actual efficiency of each approach and reinforce the asymptotic analysis of our algorithms.

Description: Pǎtraşcu (STOC ’10) reduces the \(\mathrm {3SUM}\)  problem to listing triangles in a graph. In the other direction, we show that if one can solve \(\mathrm {3SUM}\) on a set of size \(n\) in time \(n^{1+\epsilon }\) then one can list \(t\) triangles in a graph with \(m\) edges in time \(\tilde{O}(m^{1+\epsilon }t^{1/3-\epsilon /3})\) . Our result builds on and extends works by the Paghs (PODS ’06) and by Vassilevska and Williams (FOCS ’10). We make our reductions deterministic using tools from pseudorandomness. We then re-execute both Pǎtraşcu’s reduction and ours for the variant \(\mathrm {3XOR}\)  of \(\mathrm {3SUM}\)  where integer summation is replaced by bit-wise xor. As a corollary we obtain that if \(\mathrm {3XOR}\)  is solvable in linear time but \(\mathrm {3SUM}\)  requires quadratic randomized time, or vice versa, then the randomized time complexity of listing \(m\) triangles in a graph with \(m\) edges is \(m^{4/3}\) up to a factor \(m^\alpha \) for any \(\alpha 〉 0\) .

Description: Given a set \(S = \{s_1, s_2, \ldots , s_n\}\) of strings of equal length \(L\) and an integer \(d\) , the closest string problem (CSP) requires the computation of a string \(s\) of length \(L\) such that \(d(s, s_i) \le d\) for each \(s_i \in S\) , where \(d(s, s_i)\) is the Hamming distance between \(s\) and \(s_i\) . The problem is NP-hard and has been extensively studied in the context of approximation algorithms and fixed-parameter algorithms. Fixed-parameter algorithms provide the most practical solutions to its real-life applications in bioinformatics. In this paper we develop the first randomized fixed-parameter algorithms for CSP. Not only are the randomized algorithms much simpler than their deterministic counterparts, their time complexities are also significantly better than the previously best known (deterministic) algorithms.

Description: We present an efficient algorithm for testing outerplanarity of graphs in the bounded-degree model. In this model, given a graph \(G\) with degree bound \(d\) , we should distinguish with high probability the case that \(G\) is outerplanar from the case that modifying at least an \(\epsilon \) -fraction of the edge set is necessary to make \(G\) outerplanar. Our algorithm runs in time polynomial in \(d\) and \(\frac{1}{\epsilon }\) only. To achieve the time complexity, we exploit the tree-like structure inherent to an outerplanar graph using the microtree/macrotree decomposition of a tree. As a corollary, we show that the property of being a cactus is testable in time polynomial in \(d\) and \(\frac{1}{\epsilon }\) .

Description: In many communications settings, such as wired and wireless local-area networks, when multiple users attempt to access a communication channel at the same time, a conflict results and none of the communications are successful. Contention resolution is the study of distributed transmission and retransmission protocols designed to maximize notions of utility such as channel utilization in the face of blocking communications. An additional issue to be considered in the design of such protocols is that selfish users may have incentive to deviate from the prescribed behavior, if another transmission strategy increases their utility. The work of Fiat et al. (in SODA ’07, pp. 179–188, SIAM, Philadelphia 2007 ) addresses this issue by constructing an asymptotically optimal incentive-compatible protocol. However, their protocol assumes the cost of any single transmission is zero, and the protocol completely collapses under non-zero transmission costs. In this paper we treat the case of non-zero transmission cost c . We present asymptotically optimal contention resolution protocols that are robust to selfish users, in two different channel feedback models. Our main result is in the Collision Multiplicity Feedback model, where after each time slot, the number of attempted transmissions is returned as feedback to the users. In this setting, we give a protocol that has expected cost Θ ( n + c log n ) and is in o (1)-equilibrium, where n is the number of users.

Description: We consider the \(k\) -strong conflict-free ( \(k\) -SCF) coloring of a set of points on a line with respect to a family of intervals: Each point on the line must be assigned a color so that the coloring is conflict-free in the following sense: in every interval \(I\) of the family there are at least \(k\) colors each appearing exactly once in \(I\) . We first present a polynomial-time approximation algorithm for the general problem; the algorithm has approximation ratio 2 when \(k=1\) and \(5-\frac{2}{k}\) when \(k\ge 2\) . In the special case of a family that contains all possible intervals on the given set of points, we show that a 2-approximation algorithm exists, for any \(k \ge 1\) . We also provide, in case \(k=O({{\mathrm{polylog}}}(n))\) , a quasipolynomial time algorithm to decide the existence of a \(k\) -SCF coloring that uses at most \(q\) colors.

Description: Threats on the stability of a financial system may severely affect the functioning of the entire economy, and thus considerable emphasis is placed on the analyzing the cause and effect of such threats. The financial crisis in the current and past decade has shown that one important cause of instability in global markets is the so-called financial contagion , namely the spreadings of instabilities or failures of individual components of the network to other, perhaps healthier, components. This leads to a natural question of whether the regulatory authorities could have predicted and perhaps mitigated the current economic crisis by effective computations of some stability measure of the banking networks. Motivated by such observations, we consider the problem of defining and evaluating stabilities of both homogeneous and heterogeneous banking networks against propagation of synchronous idiosyncratic shocks given to a subset of banks. We formalize the homogeneous banking network model of Nier et al. (J. Econ. Dyn. Control 31:2033–2060, 2007 ) and its corresponding heterogeneous version, formalize the synchronous shock propagation procedures outlined in (Nier et al. J. Econ. Dyn. Control 31:2033–2060, 2007 ; M. Eboli Mimeo, 2004 ), define two appropriate stability measures and investigate the computational complexities of evaluating these measures for various network topologies and parameters of interest. Our results and proofs also shed some light on the properties of topologies and parameters of the network that may lead to higher or lower stabilities.

Description: We study the two-dimensional bin packing problem: Given a list of \(n\) rectangles the objective is to find a feasible, i.e. axis-parallel and non-overlapping, packing of all rectangles into the minimum number of unit sized squares, also called bins. Our problem consists of two versions; in the first version it is not allowed to rotate the rectangles while in the other it is allowed to rotate the rectangles by \(90^{\circ }\) , i.e. to exchange the widths and the heights. Two-dimensional bin packing is a generalization of its one-dimensional counterpart and is therefore strongly \(\mathcal {NP}\) -hard. Furthermore Bansal et al. (Math Oper Res 31(1):31–49, 2006 ) showed that even an \(\mathcal {APTAS}\) is ruled out for this problem, unless \(\mathcal {P}=\mathcal {NP}\) . This lower bound of asymptotic approximability was improved by Chlebík and Chlebíková (J Discrete Algorithms 7(3):291–305, 2009 ) to values \(1+1/3792\) and \(1+1/2196\) for the version with and without rotations, respectively. On the positive side there is an asymptotic 1.69.. approximation by Caprara (Math Oper Res 33:203–215, 2008 ) without rotations and an asymptotic 1.52... approximation by Bansal et al. (SIAM J Comput 39(4):1256–1278, 2009 ) for both versions. We give a new asymptotic upper bound for both versions of our problem: For any fixed \(\varepsilon \) and any instance that fits optimally into \(\mathrm {OPT}\) bins, our algorithm computes a packing into \((3/2+\varepsilon )\cdot \mathrm {OPT}+69\) bins in the version without rotations and \((3/2+\varepsilon )\cdot \mathrm {OPT}+39\) bins in the version with rotations. The algorithm has polynomial running time in the input length. In our new technique we consider an optimal packing of the rectangles into the bins. We cut a small vertical or horizontal strip out of each bin and move the intersecting rectangles into additional bins. This enables us to either round the widths of all wide rectangles, or the heights of all long rectangles in this bin. After this step we round the other unrounded side of these rectangles and we achieve a solution with a simple structure and only few types of rectangles. Our algorithm initially rounds the instance and computes a solution that nearly matches the modified optimal solution.

Description: The Hospitals/Residents problem is a many-to-one extension of the stable marriage problem. In an instance, each hospital specifies a quota, i.e., an upper bound on the number of positions it provides. It is well-known that in any instance, there exists at least one stable matching, and finding one can be done in polynomial time. In this paper, we consider an extension in which each hospital specifies not only an upper bound but also a lower bound on its number of positions. In this setting, there can be instances that admit no stable matching, but the problem of asking if there is a stable matching is solvable in polynomial time. In case there is no stable matching, we consider the problem of finding a matching that is “as stable as possible”, namely, a matching with a minimum number of blocking pairs. We show that this problem is hard to approximate within the ratio of \((|H|+|R|)^{1-\epsilon }\) for any positive constant \(\epsilon \) where \(H\) and \(R\) are the sets of hospitals and residents, respectively. We then tackle this hardness from two different angles. First, we give an exponential-time exact algorithm whose running time is \(O((|H||R|)^{t+1})\) , where \(t\) is the number of blocking pairs in an optimal solution. Second, we consider another measure for optimization criteria, i.e., the number of residents who are involved in blocking pairs. We show that this problem is still NP-hard but has a polynomial-time \(\sqrt{|R|}\) -approximation algorithm.

Description: We consider the online bin packing problem under the advice complexity model where the “online constraint” is relaxed and an algorithm receives partial information about the future items. We provide tight upper and lower bounds for the amount of advice an algorithm needs to achieve an optimal packing. We also introduce an algorithm that, when provided with \(\log n + o(\log n)\) bits of advice, achieves a competitive ratio of \(3/2\) for the general problem. This algorithm is simple and is expected to find real-world applications. We introduce another algorithm that receives \(2n + o(n)\) bits of advice and achieves a competitive ratio of \(4/3 + \varepsilon \) . Finally, we provide a lower bound argument that implies that advice of linear size is required for an algorithm to achieve a competitive ratio better than 9/8.

Description: We consider online preemptive scheduling of jobs with fixed starting times revealed at those times on \(m\) uniformly related machines, with the goal of maximizing the total weight of completed jobs. Every job has a size and a weight associated with it. A newly released job must be either assigned to start running immediately on a machine or otherwise it is dropped. It is also possible to drop an already scheduled job, but only completed jobs contribute their weights to the profit of the algorithm. In the most general setting, no algorithm has bounded competitive ratio, and we consider a number of standard variants. We give a full classification of the variants into cases which admit constant competitive ratio (weighted and unweighted unit jobs, and C-benevolent instances, which is a wide class of instances containing proportional-weight jobs), and cases which admit only a linear competitive ratio (unweighted jobs and D-benevolent instances). In particular, we give a lower bound of \(m\) on the competitive ratio for scheduling unit weight jobs with varying sizes, which is tight. For unit size and weight we show that a natural greedy algorithm is \(4/3\) -competitive and optimal on \(m=2\) machines, while for large \(m\) , its competitive ratio is between \(1.56\) and \(2\) . Furthermore, no algorithm is better than \(1.5\) -competitive.

Description: Binary jumbled pattern matching asks to preprocess a binary string \(S\) in order to answer queries \((i,j)\) which ask for a substring of \(S\) that is of length \(i\) and has exactly \(j\) 1-bits. This problem naturally generalizes to vertex-labeled trees and graphs by replacing “substring” with “connected subgraph”. In this paper, we give an \(O(n^2 / \log ^2 n)\) -time solution for trees, matching the currently best bound for (the simpler problem of) strings. We also give an \({O}({g^{2 / 3} n^{4 / 3}/(\log n)^{4/3}})\) -time solution for strings that are compressed by a context-free grammar of size \(g\) in Chomsky normal form. This solution improves the known bounds when the string is compressible under many popular compression schemes. Finally, we prove that on graphs the problem is fixed-parameter tractable with respect to the treewidth \(w\) of the graph, even for a constant number of different vertex-labels, thus improving the previous best \(n^{O(w)}\) algorithm.

Description: The class \(\text {q-Horn}\) , introduced by Boros, Crama and Hammer in 1990, is one of the largest known classes of propositional CNF formulas for which satisfiability can be decided in polynomial time. This class properly contains the fundamental classes of Horn and 2-CNF formulas as well as the class of renamable (or disguised) Horn formulas. In this paper we extend this class so that its favorable algorithmic properties can be made accessible to formulas that are outside but “close” to this class. We show that deciding satisfiability is fixed-parameter tractable parameterized by the distance of the given formula from \(\text {q-Horn}\) . The distance is measured by the smallest number of variables that we need to delete from the formula in order to get a \(\text {q-Horn}\) formula, i.e., the size of a smallest deletion backdoor set into the class \(\text {q-Horn}\) . This result generalizes known fixed-parameter tractability results for satisfiability decision with respect to the parameters distance from Horn, 2-CNF, and renamable Horn.

Description: In this paper we study the problem of estimating the number of occurrences of substrings in textual data: A text \(T\) on some alphabet \(\varSigma =[\sigma ]\) of length \(n\) is preprocessed and an index \({\mathcal {I}}\) is built. The index is used in lieu of the text to answer queries of the form \(\mathsf{Count}\approx (P)\) , returning an approximated number of the occurrences of an arbitrary pattern \(P\) as a substring of \(T\) . The problem has its main application in selectivity estimation related to the LIKE predicate in textual databases. Our focus is on obtaining an algorithmic solution with guaranteed error rates and small footprint. To achieve that, we first enrich previous work in the area of compressed text-indexing providing an optimal data structure that, for a given additive error \(\ell \ge 1\) , requires \(\varTheta \left( \frac{n}{\ell }\log \sigma \right) \) bits. We also approach the issue of guaranteeing exact answers for sufficiently frequent patterns, providing a data structure whose size scales with the amount of such patterns. Our theoretical findings are supported by experiments showing the practical impact of our data structures.

Description: In this paper we consider word equations with one-variable (and arbitrarily many occurrences of it). A recent technique of recompression, which is applicable to general word equations, is shown to be suitable also in this case. While in general case the recompression is nondeterministic in case of one-variable it becomes deterministic and its running time is \(\mathcal {O}(n + \#_X \log n)\) , where \(\#_X\) is the number of occurrences of the variable in the equation. This matches the previously best algorithm due to Dąbrowski and Plandowski. Then, using a couple of heuristics as well as more detailed time analysis, the running time is lowered to \(\mathcal {O}(n)\) in the RAM model. Unfortunately, no new properties of solutions are shown.

Description: The scaffold filling problem aims to set up the whole genomes by filling those missing genes into the scaffolds to optimize a similarity measure of genomes. A typical and frequently used measure for the similarity of two genomes is the number of common adjacencies. One-sided scaffold filling is given by a scaffold and a whole genome, and asks to fill the missing genes into that scaffold to result in such a genome that the number of common adjacencies between it and the given genome is maximized. Two-sided scaffold filling is given by two scaffolds, and asks to fill the missing genes into those two scaffolds respectively to result in such two genomes that the number of common adjacencies between them is maximized. One-sided scaffold filling can be approximated to \(\frac{5}{4}\) by now. However, the algorithmic progress for two-sided scaffold filling seems rare. What we know for two-sided scaffold filling is a 2-approximation algorithm by now. In this paper, we propose a new algorithm for two-sided scaffold filling which can achieve a performance ratio of \(\frac{3}{2}\) in \(O(N^3)\) time, where \(N\) is the number of genes in an output genome. An example can be given to show that the performance ratio \(\frac{3}{2}\) for this algorithm is actually tight.

Description: Logit choice dynamics constitute a family of randomized best response dynamics based on the logit choice function (McFadden in Frontiers in econometrics. Academic Press, New York, 1974 ) that models players with limited rationality and knowledge. In this paper we study the all-logit dynamics [also known as simultaneous learning (Alós-Ferrer and Netzer in Games Econ Behav 68(2):413–427, 2010 )], where at each time step all players concurrently update their strategies according to the logit choice function. In the well studied (one-)logit dynamics (Blume in Games Econ Behav 5(3):387–424, 1993 ) instead at each step only one randomly chosen player is allowed to update. We study properties of the all-logit dynamics in the context of local interaction potential games , a class of games that has been used to model complex social phenomena (Montanari and Saberi 2009 ; Peyton in The economy as a complex evolving system. Oxford University Press, Oxford, 2003 ) and physical systems (Levin et al. in Probab Theory Relat Fields 146(1–2):223–265, 2010 ; Martinelli in Lectures on probability theory and statistics. Springer, Berlin, 1999 ). In a local interaction potential game players are the vertices of a social graph whose edges are two-player potential games. Each player picks one strategy to be played for all the games she is involved in and the payoff of the player is the sum of the payoffs from each of the games. We prove that local interaction potential games characterize the class of games for which the all-logit dynamics is reversible. We then compare the stationary behavior of one-logit and all-logit dynamics. Specifically, we look at the expected value of a notable class of observables, that we call decomposable observables. We prove that the difference between the expected values of the observables at stationarity for the two dynamics depends only on the rationality level \(\beta \) and on the distance of the social graph from a bipartite graph. In particular, if the social graph is bipartite then decomposable observables have the same expected value. Finally, we show that the mixing time of the all-logit dynamics has the same twofold behavior that has been highlighted in the case of the one-logit: for some games it exponentially depends on the rationality level \(\beta \) , whereas for other games it can be upper bounded by a function independent from \(\beta \) .

Description: Let \(b\in {\mathbb {N}}_{\ge 1}\) and let \({\mathcal {H}}=(V,{\mathcal {E}})\) be a hypergraph with maximum vertex degree \({\varDelta }\) and maximum edge size \(l\) . A set \(b\) -multicover in \({\mathcal {H}}\) is a set of edges \(C \subseteq {\mathcal {E}}\) such that every vertex in \(V\) belongs to at least \(b\) edges in \(C\) . \({\textsc {set }}\, b\text {-}{\textsc {multicover}}\) is the problem of finding a set \(b\) -multicover of minimum cardinality, and for \(b=1\) it is the fundamental set cover problem. Peleg et al. (Algorithmica 18(1):44–66, 1997 ) gave a randomized algorithm achieving an approximation ratio of \(\delta \cdot \big (1-\big (\frac{c}{n}\big )^\frac{1}{\delta }\big )\) , where \(\delta := {\varDelta }- b + 1\) and \(c〉0\) is a constant. As this ratio depends on the instance size \(n\) and tends to \(\delta \) as \(n\) tends to \(\infty \) , it remained an open problem whether an approximation ratio of \(\delta \alpha \) with a constant \(\alpha 〈 1\) can be proved. In fact, the authors conjectured that for any fixed \({\varDelta }\) and \(b\) , the problem is not approximable within a ratio smaller than \(\delta \) , unless \({\mathcal {P}}={\mathcal {NP}}\) . We present a randomized algorithm of hybrid type for \({\textsc {set }}\, b\text {-}{\textsc {multicover}}\) , \(b \ge 2\) , combining LP-based randomized rounding with greedy repairing, and achieve an approximation ratio of \(\delta \cdot \left( 1 - \frac{11({\varDelta }- b)}{72l} \right) \) for hypergraphs with maximum edge size \(l \in {\mathcal {O}}\left( \max \big \{(nb)^\frac{1}{5},n^\frac{1}{4}\big \}\right) \) . In particular, for all hypergraphs where \(l\) is constant , we get an \(\alpha \delta \) -ratio with constant \(\alpha 〈 1\) . Hence the above stated conjecture does not hold for hypergraphs with constant \(l\) and we have identified the boundedness of the maximum hyperedge size as a relevant parameter responsible for approximations below \(\delta \) .

Description: The Art Gallery Problem (AGP) asks for placing a minimum number of stationary guards in a polygonal region \(P\) , such that all points in \(P\) are guarded. The problem is known to be NP-hard, and its inherent continuous structure (with both the set of points that need to be guarded and the set of points that can be used for guarding being uncountably infinite) makes it difficult to apply a straightforward formulation as an integer linear program. We use an iterative primal-dual relaxation approach for solving AGP instances to optimality. At each stage, a pair of LP relaxations for a finite candidate subset of primal covering and dual packing constraints and variables is considered; these correspond to possible guard positions and points that are to be guarded. Particularly useful are cutting planes for eliminating fractional solutions. We identify two classes of facets, based on Edge Cover and Set Cover (SC) inequalities. Solving the separation problem for the latter is NP-complete, but exploiting the underlying geometric structure, we show that large subclasses of fractional SC solutions cannot occur for the AGP. This allows us to separate the relevant subset of facets in polynomial time. We also characterize all facets for finite AGP relaxations with coefficients in \(\{0, 1, 2\}\) . Finally, we demonstrate the practical usefulness of our approach. Our cutting plane technique yields a significant improvement in terms of speed and solution quality due to considerably reduced integrality gaps as compared to the approach by Kröller et al. (ACM J Exp Algorithm 17(1): 2.3:2.1–2.3:2.23, 2012 ).

Description: We consider systems of small, cheap, simple sensors that are organized in a distributed network and used for estimating and tracking the locations of targets. The objective is to assign sensors to targets such that the overall expected error of the sensors’ estimates of the target locations is minimized. The so-called focus of attention problem (FOA) deals with the special case where every target is tracked by one pair of range sensors. The resulting computational problem is a special case of the axial three-index assignment problem, a well-known fundamental problem in combinatorial optimization. We provide a complete complexity and approximability analysis of the FOA problem: we establish strong NP-hardness and the unlikeliness of an FPTAS, we identify polynomially solvable special cases, and we construct a sophisticated polynomial time approximation scheme for it.

Description: We study parameterized complexity of a generalization of the classical Feedback Vertex Set problem, namely the Group Feedback Vertex Set problem: we are given a graph \(G\) with edges labeled with group elements, and the goal is to compute the smallest set of vertices that hits all cycles of \(G\) that evaluate to a non-null element of the group. This problem generalizes not only Feedback Vertex Set , but also Subset Feedback Vertex Set , Multiway Cut and Odd Cycle Transversal . Completing the results of Guillemot (Discrete Optim 8(1):61–71, 2011 ), we provide a fixed-parameter algorithm for the parameterization by the size of the cutset only. Our algorithm works even if the group is given as a blackbox performing group operations.

Description: We show that the following two problems are fixed-parameter tractable with parameter \(k\) : testing whether a connected \(n\) -vertex graph with \(m\) edges has a square root with at most \(n-1+k\) edges and testing whether such a graph has a square root with at least \(m-k\) edges. Our first result implies that squares of graphs obtained from trees by adding at most \(k\) edges can be recognized in polynomial time for every fixed \(k\ge 0\) ; previously this result was known only for \(k=0\) . Our second result is equivalent to stating that deciding whether a graph can be modified into a square root of itself by at most \(k\) edge deletions is fixed-parameter tractable with parameter \(k\) .

Description: We study the following separation problem: given \(n\) connected curves and two points \(s\) and \(t\) in the plane, compute the minimum number of curves one needs to retain so that any path connecting \(s\) to \(t\) intersects some of the retained curves. We give the first polynomial \((\fancyscript{O}(n^3))\) time algorithm for the problem, assuming that the curves have reasonable computational properties. The algorithm is based on considering the intersection graph of the curves, defining an appropriate family of closed walks in the intersection graph that satisfies the 3-path-condition, and arguing that a shortest cycle in the family gives an optimal solution. The 3-path-condition has been used mainly in topological graph theory, and thus its use here makes the connection to topology clear. We also show that the generalized version, where several input points are to be separated, is NP-hard for natural families of curves, like segments in two directions or unit circles.

Description: The subset sum algorithm is a natural heuristic for the classical Bin Packing problem: In each iteration, the algorithm finds among the unpacked items, a maximum size set of items that fits into a new bin. More than 35 years after its first mention in the literature, establishing the worst-case performance of this heuristic remains, surprisingly, an open problem. Due to their simplicity and intuitive appeal, greedy algorithms are the heuristics of choice of many practitioners. Therefore, better understanding simple greedy heuristics is, in general, an interesting topic in its own right. Very recently, Epstein and Kleiman (Proc. ESA 2008, pp. 368–380) provided another incentive to study the subset sum algorithm by showing that the Strong Price of Anarchy of the game theoretic version of the Bin Packing problem is precisely the approximation ratio of this heuristic. In this paper we establish the exact approximation ratio of the subset sum algorithm, thus settling a long standing open problem. We generalize this result to the parametric variant of the Bin Packing problem where item sizes lie on the interval \((0, \alpha ]\) for some \(\alpha \le 1\) , yielding tight bounds for the Strong Price of Anarchy for all \(\alpha \le 1\) . Finally, we study the pure Price of Anarchy of the parametric Bin Packing game for which we show nearly tight upper and lower bounds for all \(\alpha \le 1\) .

Description: We present \(O(n)\) -space data structures to support various range frequency queries on a given array \(A[0:n-1]\) or tree \(T\) with \(n\) nodes. Given a query consisting of an arbitrary pair of pre-order rank indices \((i,j)\) , our data structures return a least frequent element, mode, \(\alpha \) -minority, or top- \(k\) colors (values) of the multiset of elements in the unique path with endpoints at indices \(i\) and \(j\) in \(A\) or \(T\) . We describe a data structure that supports range least frequent element queries on arrays in \(O(\sqrt{n / w})\) time, improving the \({\varTheta }(\sqrt{n})\) worst-case time required by the data structure of Chan et al. (SWAT 2012 ), where \(w \in {\varOmega }(\log n)\) is the word size in bits. We describe a data structure that supports path mode queries on trees in \(O(\log \log n \sqrt{n / w})\) time, improving the \({\varTheta }(\sqrt{n} \log n)\) worst-case time required by the data structure of Krizanc et al. (ISAAC 2003 ). We describe the first data structures to support path least frequent element queries, path \(\alpha \) -minority queries, and path top- \(k\) color queries on trees in \(O(\log \log n \sqrt{n/w}),\,O(\alpha ^{-1} \log \log n)\) , and \(O(k)\) time, respectively, where \(\alpha \in [0,1]\) and \(k \in \{1,\ldots , n\}\) are specified at query time.

Description: The parameterized complexity of a problem is generally considered “settled” once it has been shown to be fixed-parameter tractable or to be complete for a class in a parameterized hierarchy such as the weft hierarchy. Several natural parameterized problems have, however, resisted such a classification. In the present paper we argue that, in some cases, this is due to the fact that the parameterized complexity of these problems can be better understood in terms of their parameterized space or parameterized circuit complexity. This includes well-studied, natural problems like the feedback vertex set problem, the associative generability problem, or the longest common subsequence problem. We show that these problems lie in and may even be complete for different parameterized space classes, leading to new insights into the problems’ complexity. The classes we study are defined in terms of different forms of bounded nondeterminism and simultaneous time–space bounds.

Description: We present multikey quickselect: an efficient, in-place, easy-to-implement algorithm for the selection problem for strings. We analyze its expected cost under a uniform model, measured as the number of character comparisons and pointer swaps, depending on the alphabet cardinality. From the analysis, we derive a binary variant of the algorithm, which is more efficient when the range of values for the alphabet is known. This variant can also be applied to multikey quicksort.

Description: Circle graphs are the intersection graphs of chords in a circle. This paper presents the first sub-quadratic recognition algorithm for the class of circle graphs. Our algorithm is O ( n + m ) times the inverse Ackermann function, α ( n + m ), whose value is smaller than 4 for any practical graph. The algorithm is based on a new incremental Lexicographic Breadth-First Search characterization of circle graphs, and a new efficient data-structure for circle graphs, both developed in the paper. The algorithm is an extension of a Split Decomposition algorithm with the same running time developed by the authors in a companion paper.

Description: A spanning tree T of a graph G is called a tree t - spanner of G if the distance between every pair of vertices in T is at most t times their distance in G . In this paper, we present an algorithm which constructs for an n -vertex m -edge unweighted graph G : a tree (2⌊log 2 n ⌋)-spanner in O ( m log n ) time, if G is a chordal graph (i.e., every induced cycle of G has length 3); a tree (2 ρ ⌊log 2 n ⌋)-spanner in O ( mn log 2 n ) time or a tree (12 ρ ⌊log 2 n ⌋)-spanner in O ( m log n ) time, if G is a graph admitting a Robertson-Seymour’s tree-decomposition with bags of radius at most ρ in G ; and a tree (2⌈ t /2⌉⌊log 2 n ⌋)-spanner in O ( mn log 2 n ) time or a tree (6 t ⌊log 2 n ⌋)-spanner in O ( m log n ) time, if G is an arbitrary graph admitting a tree t -spanner. For the latter result we use a new necessary condition for a graph to have a tree t -spanner: if a graph G has a tree t -spanner, then G admits a Robertson-Seymour’s tree-decomposition with bags of radius at most ⌈ t /2⌉ and diameter at most t in G .

Description: We consider the problem of supporting rank and select operations on a bit vector of length m with n 1-bits. The problem is considered in the succinct index model, where the bit vector is stored in “read-only” memory and an additional data structure, called the index is created during pre-processing to help answer the above queries. We give asymptotically optimal density-sensitive trade-offs, involving both m and  n , that relate the size of the index to the number of accesses to the bit vector (and processing time) needed to answer the above queries. The results are particularly interesting for the case where n = o ( m ).

Description: The hash table, especially its external memory version, is one of the most important index structures in large databases. Assuming a truly random hash function, it is known that in a standard external hash table with block size b , searching for a particular key only takes expected average t q =1+1/2 Ω ( b ) disk accesses for any load factor α bounded away from 1. However, such near-perfect performance is achieved only when b is known and the hash table is particularly tuned for working with such a blocking. In this paper we study if it is possible to build a cache-oblivious hash table that works well with any blocking. Such a hash table will automatically perform well across all levels of the memory hierarchy and does not need any hardware-specific tuning, an important feature in autonomous databases. We first show that linear probing, a classical collision resolution strategy for hash tables, can be easily made cache-oblivious but it only achieves t q =1+ Θ ( α / b ) even if a truly random hash function is used. Then we demonstrate that the block probing algorithm (Pagh et al. in SIAM Rev. 53(3):547–558, 2011 ) achieves t q =1+1/2 Ω ( b ) , thus matching the cache-aware bound, if the following two conditions hold: (a) b is a power of 2; and (b) every block starts at a memory address divisible by b . Note that the two conditions hold on a real machine, although they are not stated in the cache-oblivious model. Interestingly, we also show that neither condition is dispensable: if either of them is removed, the best obtainable bound is t q =1+ O ( α / b ), which is exactly what linear probing achieves.

Description: We consider the facility location problem with submodular penalties (FLPSP) and the facility location problem with linear penalties (FLPLP), two extensions of the classical facility location problem (FLP). First, we introduce a general algorithmic framework for a class of covering problems with submodular penalties, extending the recent result of Geunes et al. (Math Program 130:85–106, 2011 ) with linear penalties. This framework leverages existing approximation results for the original covering problems to obtain corresponding results for their counterparts with submodular penalties. Specifically, any LP-based \(\alpha \) -approximation for the original covering problem can be leveraged to obtain an \(\left( 1-e^{-1/\alpha }\right) ^{-1}\) -approximation algorithm for the counterpart with submodular penalties. Consequently, any LP-based approximation algorithm for the classical FLP (as a covering problem) can yield, via this framework, an approximation algorithm for the counterpart with submodular penalties. Second, by exploiting some special properties of submodular/linear penalty function, we present an LP rounding algorithm which has the currently best \(2\) -approximation ratio over the previously best \(2.375\) by Li et al. (Theoret Comput Sci 476:109–117, 2013 ) for the FLPSP and another LP-rounding algorithm which has the currently best \(1.5148\) -approximation ratio over the previously best \(1.853\) by Xu and Xu (J Comb Optim 17:424–436, 2008 ) for the FLPLP, respectively.

Description: A factor \(u\) of a word \(w\) is a cover of \(w\) if every position in \(w\) lies within some occurrence of \(u\) in \(w\) . A word \(w\) covered by \(u\) thus generalizes the idea of a repetition , that is, a word composed of exact concatenations of \(u\) . In this article we introduce a new notion of \(\alpha \) - partial cover , which can be viewed as a relaxed variant of cover, that is, a factor covering at least \(\alpha \) positions in \(w\) . We develop a data structure of \(\mathcal {O}(n)\) size (where \(n=|w|\) ) that can be constructed in \(\mathcal {O}(n\log n)\) time which we apply to compute all shortest \(\alpha \) -partial covers for a given \(\alpha \) . We also employ it for an \(\mathcal {O}(n\log n)\) -time algorithm computing a shortest \(\alpha \) -partial cover for each \(\alpha =1,2,\ldots ,n\) .

Description: We consider a two-edge connected, non-negatively real-weighted graph G with n vertices and m edges, and a single-source shortest paths tree (SPT) of G rooted at an arbitrary vertex. If an edge of the SPT is temporarily removed, a widely recognized approach to reconnect the vertices disconnected from the root consists of joining the two resulting subtrees by means of a single non-tree edge, called a swap edge . This allows to reduce consistently the set-up and computational costs which are incurred if one instead rebuilds a new optimal SPT from scratch. In the past, several optimality criteria have been considered to select a best possible swap edge, and here we restrict our attention to arguably the two most significant measures: the minimization of either the maximum or the average distance between the root and the disconnected vertices. For the former criteria, we present an \(O(m \log \alpha (m,n))\) time algorithm—where \(\alpha \) is the inverse of the Ackermann function—to find a best swap edge for every edge of the SPT, thus improving onto the previous \(O(m \log n)\) time algorithm. Concerning the latter criteria, we provide an \(O(m+n \log n)\) time algorithm for the special but important case where G is unweighted , which compares favourably with the \(O\left( m+n \, \alpha (n,n)\log ^2n\right) \) time bound that one would get by using the fastest algorithm known for the weighted case—once this is suitably adapted to the unweighted case.

Description: In the Min-Sum 2-Clustering problem, we are given a graph and a parameter k , and the goal is to determine if there exists a 2-partition of the vertex set such that the total conflict number is at most k , where the conflict number of a vertex is the number of its non-neighbors in the same cluster and neighbors in the different cluster. The problem is equivalent to 2-Cluster Editing and 2-Correlation Clustering with an additional multiplicative factor two in the cost function. In this paper we show an algorithm for Min-Sum 2-Clustering with time complexity O ( n ⋅2.619 r /(1−4 r / n ) + n 3 ), where n is the number of vertices and r = k / n . Particularly, the time complexity is O ∗ (2.619 k / n ) for k ∈ o ( n 2 ) and polynomial for k ∈ O ( n log n ), which implies that the problem can be solved in subexponential time for k ∈ o ( n 2 ). We also design a parameterized algorithm for a variant in which the cost is the sum of the squared conflict-numbers. For k ∈ o ( n 3 ), the algorithm runs in subexponential O ( n 3 ⋅5.171 θ ) time, where $\theta=\sqrt{k/n}$ .

Description: We prove a general reduction theorem which allows us to extend bounds for certain graph parameters on cubic graphs to bounds for general graphs taking into account the individual vertex degrees. As applications, we give an algorithm for Max $2$ -CSP whose complexity matches the algorithm of Scott and Sorkin in the case of $d$ -regular graphs, $d \le 5$ , but is otherwise faster. It also improves on the previously fastest known algorithm in terms of the average degree, given by Golovnev and Kutzkov. Also from the general theorem, we derive a bound for the pathwidth of a general graph which equals that of Fomin et al. and Gaspers for graphs of degree at most $6$ , but is smaller otherwise, and use this to give an improved exponential-space algorithm for Max $2$ -CSP. Finally we use the general result to give a faster algorithm for Max $2$ -CSP on claw-free graphs.

Description: Topic modeling is a generalization of clustering that posits that observations (words in a document) are generated by multiple latent factors (topics), as opposed to just one. The increased representational power comes at the cost of a more challenging unsupervised learning problem for estimating the topic-word distributions when only words are observed, and the topics are hidden. This work provides a simple and efficient learning procedure that is guaranteed to recover the parameters for a wide class of multi-view models and topic models, including latent Dirichlet allocation (LDA). For LDA, the procedure correctly recovers both the topic-word distributions and the parameters of the Dirichlet prior over the topic mixtures, using only trigram statistics (i.e., third order moments, which may be estimated with documents containing just three words). The method is based on an efficiently computable orthogonal tensor decomposition of low-order moments.

Description: We describe a framework for designing efficient active learning algorithms that are tolerant to random classification noise and are differentially-private. The framework is based on active learning algorithms that are statistical in the sense that they rely on estimates of expectations of functions of filtered random examples. It builds on the powerful statistical query framework of Kearns (JACM 45(6):983–1006, 1998 ). We show that any efficient active statistical learning algorithm can be automatically converted to an efficient active learning algorithm which is tolerant to random classification noise as well as other forms of “uncorrelated” noise. The complexity of the resulting algorithms has information-theoretically optimal quadratic dependence on \(1/(1-2\eta )\) , where \(\eta \) is the noise rate. We show that commonly studied concept classes including thresholds, rectangles, and linear separators can be efficiently actively learned in our framework. These results combined with our generic conversion lead to the first computationally-efficient algorithms for actively learning some of these concept classes in the presence of random classification noise that provide exponential improvement in the dependence on the error \(\epsilon \) over their passive counterparts. In addition, we show that our algorithms can be automatically converted to efficient active differentially-private algorithms. This leads to the first differentially-private active learning algorithms with exponential label savings over the passive case.

Description: Given an interval graph and integer \(k\) , we consider the problem of finding a subgraph of size \(k\) with a maximum number of induced edges, called densest k -subgraph problem in interval graphs . This problem is NP-hard even for chordal graphs (Perl and Corneil in Discret Appl Math 9(1):27–39, 1984 ), and there is probably no PTAS for general graphs (Khot and Subhash in SIAM J Comput 36(4):1025–1071, 2006 ). However, the exact complexity status for interval graphs is a long-standing open problem (Perl and Corneil in Discret Appl Math 9(1):27–39, 1984 ), and the best known approximation result is a \( 3 \) -approximation algorithm (Liazi et al. in Inf Process Lett 108(1):29–32, 2008 ). We shed light on the approximation complexity of finding a densest \( k \) -subgraph in interval graphs by presenting a polynomial-time approximation scheme (PTAS), that is, we show that there is an \( (1+\epsilon ) \) -approximation algorithm for any \( \epsilon 〉 0 \) , which is the first such approximation scheme for the densest \( k \) -subgraph problem in an important graph class without any further restrictions.

Description: Given a fixed graph \(H\) , the \(H\) - Free Edge Deletion (resp., Completion, Editing ) problem asks whether it is possible to delete from (resp., add to, delete from or add to) the input graph at most \(k\) edges so that the resulting graph is \(H\) -free, i.e., contains no induced subgraph isomorphic to \(H\) . These \(H\) -free edge modification problems are well known to be fixed-parameter tractable for every fixed \(H\) . In this paper we study the incompressibility, i.e., nonexistence of polynomial kernels, for these \(H\) -free edge modification problems in terms of the structure of \(H\) , and completely characterize their nonexistence for \(H\) being paths, cycles or 3-connected graphs. We also give a sufficient condition for the nonexistence of polynomial kernels for \({\mathcal {F}}\) - Free Edge Deletion problems, where \({\mathcal {F}}\) is a finite set of forbidden induced subgraphs. As an effective tool, we have introduced an incompressible constraint satisfiability problem Propagational - \(f\) Satisfiability to express common propagational behaviors of events, and we expect the problem to be useful in studying the nonexistence of polynomial kernels in general.

Description: In resource buying games a set of players jointly buys a subset of a finite resource set \(E\) (e.g., machines, edges, or nodes in a digraph). The cost of a resource \(e\) depends on the number (or load) of players using \(e\) , and has to be paid completely by the players before it becomes available. Each player \(i\) needs at least one set of a predefined family \({\mathcal S}_i\subseteq 2^E\) to be available. Thus, resource buying games can be seen as a variant of congestion games in which the load-dependent costs of the resources can be shared arbitrarily among the players. A strategy of player \(i\) in resource buying games is a tuple consisting of one of \(i\) ’s desired configurations \(S_i\in {\mathcal S}_i\) together with a payment vector \(p_i\in {\mathbb R}^E_+\) indicating how much \(i\) is willing to contribute towards the purchase of the chosen resources. In this paper, we study the existence and computational complexity of pure Nash equilibria (PNE, for short) of resource buying games. In contrast to classical congestion games for which equilibria are guaranteed to exist, the existence of equilibria in resource buying games strongly depends on the underlying structure of the families \({\mathcal S}_i\) and the behavior of the cost functions. We show that for marginally non-increasing cost functions, matroids are exactly the right structure to consider, and that resource buying games with marginally non-decreasing cost functions always admit a PNE.

Description: This paper introduces a new data structure, called simplex tree, to represent abstract simplicial complexes of any dimension. All faces of the simplicial complex are explicitly stored in a trie whose nodes are in bijection with the faces of the complex. This data structure allows to efficiently implement a large range of basic operations on simplicial complexes. We provide theoretical complexity analysis as well as detailed experimental results. We more specifically study Rips and witness complexes.

Description: On a stream \({\fancyscript{S}}\) of two dimensional data items \((x,y)\) where \(x\) is an item identifier and \(y\) is a numerical attribute, a correlated aggregate query \(C(\sigma ,AGG,{\fancyscript{S}})\) asks to first apply a selection predicate \(\sigma \) along the \(y\) dimension, followed by an aggregation \(AGG\) along the \(x\) dimension. For selection predicates of the form \((y 〈 c)\) or \((y 〉 c)\) , where parameter \(c\) is provided at query time, we present new streaming algorithms and lower bounds for estimating correlated aggregates. Our main result is a general method that reduces the estimation of a correlated aggregate \(AGG\) to the streaming computation of \(AGG\) over an entire stream, for an aggregate that satisfies certain conditions. This results in the first sublinear space algorithms for the correlated estimation of a large family of statistics, including frequency moments. Our experimental validation shows that the memory requirements of these algorithms are significantly smaller than existing linear storage solutions, and that these achieve a fast per-record processing time. We also study the setting when items have weights. In the case when weights can be negative, we give a strong space lower bound which holds even if the algorithm is allowed up to a logarithmic number of passes over the data. We complement this with a small space algorithm which uses a logarithmic number of passes.

Description: The Induced Graph Matching problem asks to find \(k\) disjoint induced subgraphs isomorphic to a given graph  \(H\) in a given graph \(G\) such that there are no edges between vertices of different subgraphs. This problem generalizes the classical Independent Set and Induced Matching problems, among several other problems. We show that Induced Graph Matching is fixed-parameter tractable in \(k\) on claw-free graphs when \(H\) is a fixed connected graph, and even admits a polynomial kernel when  \(H\) is a complete graph. Both results rely on a new, strong, and generic algorithmic structure theorem for claw-free graphs. Complementing the above positive results, we prove \(\mathsf {W}[1]\) -hardness of Induced Graph Matching on graphs excluding \(K_{1,4}\) as an induced subgraph, for any fixed complete graph \(H\) . In particular, we show that Independent Set is \(\mathsf {W}[1]\) -hard on \(K_{1,4}\) -free graphs. Finally, we consider the complexity of Induced Graph Matching on a large subclass of claw-free graphs, namely on proper circular-arc graphs. We show that the problem is either polynomial-time solvable or \(\mathsf {NP}\) -complete, depending on the connectivity of \(H\) and the structure of \(G\) .

Description: A b-coloring of a graph is a proper coloring such that every color class contains a vertex that is adjacent to all other color classes. The b-chromatic number of a graph \(G\) , denoted by \(\chi _b(G)\) , is the maximum number \(t\) such that \(G\) admits a b-coloring with \(t\) colors. A graph  \(G\) is called b-continuous if it admits a b-coloring with \(t\) colors, for every \(t = \chi (G),\ldots ,\chi _b(G)\) , and b-monotonic if \(\chi _b(H_1) \ge \chi _b(H_2)\) for every induced subgraph \(H_1\) of \(G\) , and every induced subgraph \(H_2\) of \(H_1\) . We investigate the b-chromatic number of graphs with stability number two. These are exactly the complements of triangle-free graphs, thus including all complements of bipartite graphs. The main results of this work are the following: (1) We characterize the b-colorings of a graph with stability number two in terms of matchings with no augmenting paths of length one or three. We derive that graphs with stability number two are b-continuous and b-monotonic. (2) We prove that it is NP-complete to decide whether the b-chromatic number of co-bipartite graph is at least a given threshold. (3) We describe a polynomial time dynamic programming algorithm to compute the b-chromatic number of co-trees. (4) Extending several previous results, we show that there is a polynomial time dynamic programming algorithm for computing the b-chromatic number of tree-cographs. Moreover, we show that tree-cographs are b-continuous and b-monotonic.

Description: We study the parameterized complexity of a broad class of problems called “local graph partitioning problems” that includes the classical fixed cardinality problems as max \(k\) - vertex cover , \(k\) - densest subgraph , etc. By developing a technique that we call “greediness-for-parameterization”, we obtain fixed parameter algorithms with respect to a pair of parameters \(k\) , the size of the solution (but not its value) and \(\varDelta \) , the maximum degree of the input graph. In particular, greediness-for-parameterization improves asymptotic running times for these problems upon random separation (that is a special case of color coding) and is more intuitive and simple. Then, we show how these results can be easily extended for getting standard-parameterization results (i.e., with parameter the value of the optimal solution) for a well known local graph partitioning problem.

Description: Split decomposition of graphs was introduced by Cunningham (under the name join decomposition) as a generalization of the modular decomposition. This paper undertakes an investigation into the algorithmic properties of split decomposition. We do so in the context of graph-labelled trees (GLTs), a new combinatorial object designed to simplify its consideration. GLTs are used to derive an incremental characterization of split decomposition, with a simple combinatorial description, and to explore its properties with respect to Lexicographic Breadth-First Search (LBFS). Applying the incremental characterization to an LBFS ordering results in a split decomposition algorithm that runs in time O ( n + m ) α ( n + m ), where α is the inverse Ackermann function, whose value is smaller than 4 for any practical graph. Compared to Dahlhaus’ linear time split decomposition algorithm (Dahlhaus in J. Algorithms 36(2):205–240, 2000 ), which does not rely on an incremental construction, our algorithm is just as fast in all but the asymptotic sense and full implementation details are given in this paper. Also, our algorithm extends to circle graph recognition, whereas no such extension is known for Dahlhaus’ algorithm. The companion paper (Gioan et al. in arXiv:1104.3284 , 2011 ) uses our algorithm to derive the first sub-quadratic circle graph recognition algorithm.

Description: In this paper, we investigate how to compute the throughput of probabilistic and replicated streaming applications. We are given (i) a streaming application whose dependence graph is a linear chain; (ii) a one-to-many mapping of the application onto a fully heterogeneous target platform, where a processor is assigned at most one application stage, but where a stage can be replicated onto a set of processors; and (iii) a set of random variables modeling the computation and communication times in the mapping. We show how to compute the throughput of the application, i.e., the rate at which data sets can be processed. The problem is easy when application stages are not replicated, i.e., each application stage is assigned to a single processor: in that case the throughput is dictated by the critical hardware resource. However, when stages are replicated, i.e., each application stage may be assigned to several processors, the problem becomes surprisingly complicated: even in the deterministic case, the optimal throughput may be lower than the smallest internal resource throughput. The first contribution of the paper is to provide a general method to compute the throughput when computation and communication times, also called stage parameters, are constant or follow I.I.D. exponential laws. The second contribution is to provide bounds for the throughput when stage parameters form associated random sequences (correlation between communication and processing times of a given data set on the different application stages, i.e., a data set that takes a long time on the first stage is likely to be large, and to take a long time on the next stages), and are N.B.U.E. (New Better than Used in Expectation) variables (if an operation has already been processed for some duration, the remaining time is smaller than the processing time of a fresh operation): the throughput is bounded from below by the exponential case and bounded from above by the deterministic case. An extensive set of simulation allows us to assess the quality of the model, and to observe the actual behavior of several distributions.

Description: Graph clustering is an important problem with applications to bioinformatics, community discovery in social networks, distributed computing, and more. While most of the research in this area has focused on clustering using disjoint clusters, many real datasets have inherently overlapping clusters. We compare overlapping and non-overlapping clusterings in graphs in the context of minimizing their conductance. It is known that allowing clusters to overlap gives better results in practice. We prove that overlapping clustering may be significantly better than non-overlapping clustering with respect to conductance, even in a theoretical setting. For minimizing the maximum conductance over the clusters, we give examples demonstrating that allowing overlaps can yield significantly better clusterings, namely, one that has much smaller optimum. In addition for the min-max variant, the overlapping version admits a simple approximation algorithm, while our algorithm for the non-overlapping version is complex and yields a worse approximation ratio due to the presence of the additional constraint. Somewhat surprisingly, for the problem of minimizing the sum of conductances, we found out that allowing overlap does not help. We show how to apply a general technique to transform any overlapping clustering into a non-overlapping one with only a modest increase in the sum of conductances. This uncrossing technique is of independent interest and may find further applications in the future. We consider this work as a step toward rigorous comparison of overlapping and non-overlapping clusterings and hope that it stimulates further research in this area.

Description: Inclusion/exclusion and measure and conquer are two central techniques from the field of exact exponential-time algorithms that recently received a lot of attention. In this paper, we show that both techniques can be used in a single algorithm. This is done by looking at the principle of inclusion/exclusion as a branching rule. This inclusion/exclusion-based branching rule can be combined in a branch-and-reduce algorithm with traditional branching rules and reduction rules. The resulting algorithms can be analysed using measure and conquer allowing us to obtain good upper bounds on their running times. In this way, we obtain the currently fastest exact exponential-time algorithms for a number of domination problems in graphs. Among these are faster polynomial-space and exponential-space algorithms for #Dominating Set and Minimum Weight Dominating Set (for the case where the set of possible weight sums is polynomially bounded), and a faster polynomial-space algorithm for Domatic Number . This approach is also extended in this paper to the setting where not all requirements in a problem need to be satisfied. This results in faster polynomial-space and exponential-space algorithms for Partial Dominating Set , and faster polynomial-space and exponential-space algorithms for the well-studied parameterised problem k - Set Splitting and its generalisation k - Not-All-Equal Satisfiability .

Description: We revisit the problem of deciding whether a given curve resembles some part of a larger curve under a fixed Fréchet distance, achieving a running time of O ( nm ), for n and m being the number of segments in the two curves. This improves the long-standing result of Alt and Godau by an O (log( nm )) factor. Our solution is based on constructing a simple data structure which we call free-space map . Using this data structure, we obtain improved algorithms for several variants of the Fréchet distance problem, including the Fréchet distance between two closed curves, and the so-called minimum/maximum walk problems. We also improve the map matching algorithm of Alt et al. for the particular case in which the map is a directed acyclic graph.

Description: 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 3 ) 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 ( ϑ 2 n 5 log n ). 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 5 log n ).

Description: We address generalized versions of the Huffman and Alphabetic Tree Problem where the cost caused by each individual leaf i , instead of being linear, depends on its depth in the tree by an arbitrary function. The objective is to minimize either the total cost or the maximum cost among all leaves. We review and extend the known results in this direction and devise a number of new algorithms and hardness proofs. It turns out that the Dynamic Programming approach for the Alphabetic Tree Problem can be extended to arbitrary cost functions, resulting in a time O ( n 4 ) optimal algorithm using space O ( n 3 ). We identify classes of cost functions where the well-known trick to reduce the runtime by a factor of n via a “monotonicity” property can be applied. For the generalized Huffman Tree Problem we show that even the k -ary version can be solved by a generalized version of the Coin Collector Algorithm of Larmore and Hirschberg (in Proc. SODA’90, pp. 310–318, 1990 ) when the cost functions are nondecreasing and convex. Furthermore, we give an O ( n 2 log n ) algorithm for the worst case minimization variants of both the Huffman and Alphabetic Tree Problem with nondecreasing cost functions. Investigating the limits of computational tractability, we show that the Huffman Tree Problem in its full generality is inapproximable unless P = NP, no matter if the objective function is the sum of leaf costs or their maximum. The alphabetic version becomes NP-hard when the leaf costs are interdependent.

Description: We consider the problem of doing fast and reliable estimation of the number z of non-zero entries in a sparse boolean matrix product. This problem has applications in databases and computer algebra. Let n denote the total number of non-zero entries in the input matrices. We show how to compute a 1± ε approximation of z (with small probability of error) in expected time for any $\varepsilon〉 4/\sqrt[4]{z}$ . The previously best estimation algorithm, due to Cohen (J. Comput. Syst. Sci. 53(3):441–453, 1997 ), uses time . We also present a variant using I/Os in expectation in the cache-oblivious model. In contrast to these results, the currently best algorithms for computing a sparse boolean matrix product use time ω ( n 4/3 ) (resp.  ω ( n 4/3 / B ) I/Os), even if the result matrix is restricted to nonzero entries. Our algorithm combines the size estimation technique of Bar-Yossef et al. (Proceedings of the 6th International Workshop on Randomization and Approximation Techniques (RANDOM ’02), pp. 1–10, 2002 ) with a particular class of pairwise independent hash functions that allows the sketch of a set of the form to be computed in expected time and I/Os. We then describe how sampling can be used to maintain (independent) sketches of matrices that allow estimation to be performed in time o ( n ) if z is sufficiently large. This gives a simpler alternative to the sketching technique of Ganguly et al. (Proceedings of the 24th ACM Symposium on Principles of Database Systems (PODS ’05), pp. 259–270, 2005 ), and matches a space lower bound shown in that paper. Finally, we present experiments on real-world data sets that show the accuracy of both our methods to be significantly better than the worst-case analysis predicts.

Description: Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This class of graphs has attracted many research efforts, mainly due to its interesting structure and its numerous applications, especially in DNA sequence analysis and resource allocation, among others. In one of the most natural generalizations of tolerance graphs, namely multitolerance graphs, two tolerances are allowed for each interval—one from the left and one from the right side of the interval. Then, in its interior part, every interval tolerates the intersection with others by an amount that is a convex combination of its two border-tolerances. In the comparison of DNA sequences between different organisms, the natural interpretation of this model lies on the fact that, in some applications, we may want to treat several parts of the genomic sequences differently. That is, we may want to be more tolerant at some parts of the sequences than at others. These two tolerances for every interval—together with their convex hull—define an infinite number of the so called tolerance-intervals , which make the multitolerance model inconvenient to cope with. In this article we introduce the first non-trivial intersection model for multitolerance graphs, given by objects in the 3-dimensional space called  trapezoepipeds . Apart from being important on its own, this new intersection model proves to be a powerful tool for designing efficient algorithms. Given a multitolerance graph with  n  vertices and  m  edges along with a multitolerance representation, we present algorithms that compute a minimum coloring and a maximum clique in optimal   O ( n log n ) time, and a maximum weight independent set in  O ( m + n log n ) time. Moreover, our results imply an optimal   O ( n log n ) time algorithm for the maximum weight independent set problem on tolerance graphs, thus closing the complexity gap for this problem. Additionally, by exploiting more the new 3D-intersection model, we completely classify multitolerance graphs in the hierarchy of perfect graphs. The resulting hierarchy of classes of perfect graphs is complete , i.e. all inclusions are strict.

Description: We consider the construction of sparse covers for planar graphs and other graphs that exclude a fixed minor. We present an algorithm that gives a cover for the γ -neighborhood of each node. For planar graphs, the cover has radius less than 16 γ and degree no more than 18. For every n node graph that excludes a minor of a fixed size, we present an algorithm that yields a cover with radius no more than 4 γ and degree O (log n ). This is a significant improvement over previous results for planar graphs and for graphs excluding a fixed minor; in order to obtain clusters with radius O ( γ ), it was required to have the degree polynomial in n . Our algorithms are based on a recursive application of a basic routine called shortest-path clustering , which seems to be a novel approach to the construction of sparse covers. Since sparse covers have many applications in distributed computing, including compact routing, distributed directories, synchronizers, and Universal TSP, our improved cover construction results in improved algorithms for all these problems, for the class of graphs that exclude a fixed minor.

Description: The Contractibility problem takes as input two graphs G and H , and the task is to decide whether H can be obtained from G by a sequence of edge contractions. The Induced Minor and Induced Topological Minor problems are similar, but the first allows both edge contractions and vertex deletions, whereas the latter allows only vertex deletions and vertex dissolutions. All three problems are NP -complete, even for certain fixed graphs H . We show that these problems can be solved in polynomial time for every fixed H when the input graph G is chordal. Our results can be considered tight, since these problems are known to be W [ 1 ]-hard on chordal graphs when parameterized by the size of H . To solve Contractibility and Induced Minor , we define and use a generalization of the classic Disjoint Paths problem, where we require the vertices of each of the k paths to be chosen from a specified set. We prove that this variant is NP -complete even when k =2, but that it is polynomial-time solvable on chordal graphs for every fixed k . Our algorithm for Induced Topological Minor is based on another generalization of Disjoint Paths called Induced Disjoint Paths , where the vertices from different paths may no longer be adjacent. We show that this problem, which is known to be NP -complete when k =2, can be solved in polynomial time on chordal graphs even when k is part of the input. Our results fit into the general framework of graph containment problems, where the aim is to decide whether a graph can be modified into another graph by a sequence of specified graph operations. Allowing combinations of the four well-known operations edge deletion, edge contraction, vertex deletion, and vertex dissolution results in the following ten containment relations: (induced) minor, (induced) topological minor, (induced) subgraph, (induced) spanning subgraph, dissolution, and contraction. Our results, combined with existing results, settle the complexity of each of the ten corresponding containment problems on chordal graphs.

Description: We reconsider the well-studied Selfish Routing game with affine latency functions. The Price of Anarchy for this class of games takes maximum value 4/3; this maximum is attained already for a simple network of two parallel links, known as Pigou’s network. We improve upon the value 4/3 by means of Coordination Mechanisms. We increase the latency functions of the edges in the network, i.e., if ℓ e ( x ) is the latency function of an edge e , we replace it by $\hat{\ell}_{e}(x)$ with $\ell_{e}(x) \le \hat{\ell}_{e}(x)$ for all x . Then an adversary fixes a demand rate as input. The engineered Price of Anarchy of the mechanism is defined as the worst-case ratio of the Nash social cost in the modified network over the optimal social cost in the original network. Formally, if $\hat{C}_{N} (r)$ denotes the cost of the worst Nash flow in the modified network for rate r and C opt ( r ) denotes the cost of the optimal flow in the original network for the same rate then $$\mathit{ePoA} = \max_{r \ge 0} \frac{\hat{C}_N(r)}{C_{\mathit{opt}}(r)}. $$ We first exhibit a simple coordination mechanism that achieves for any network of parallel links an engineered Price of Anarchy strictly less than 4/3. For the case of two parallel links our basic mechanism gives 5/4=1.25. Then, for the case of two parallel links, we describe an optimal mechanism; its engineered Price of Anarchy lies between 1.191 and 1.192.

Description: Multiple-choice load balancing has been a topic of intense study since the seminal paper of Azar, Broder, Karlin, and Upfal. Questions in this area can be phrased in terms of orientations of a graph, or more generally a k -uniform random hypergraph. A ( d , b ) -orientation is an assignment of each edge to d of its vertices, such that no vertex has more than b edges assigned to it. Conditions for the existence of such orientations have been completely documented except for the “extreme” case of ( k −1,1)-orientations. We consider this remaining case, and establish: The density threshold below which an orientation exists with high probability, and above which it does not exist with high probability. An algorithm for finding an orientation that runs in linear time with high probability, with explicit polynomial bounds on the failure probability. Previously, no closed-form expression for the threshold was known. The only known algorithms for constructing ( k −1,1)-orientations worked for k ≤3, and were only shown to have expected linear running time.

Description: We describe algorithms to compute edge sequences, a shortest path map, and the Fréchet distance for a convex polyhedral surface. Distances on the surface are measured by the length of a Euclidean shortest path. We describe how the star unfolding changes as a source point slides continuously along an edge of the convex polyhedral surface. We describe alternative algorithms to the edge sequence algorithm of Agarwal et al. (SIAM J. Comput. 26(6):1689–1713, 1997 ) for a convex polyhedral surface. Our approach uses persistent trees, star unfoldings, and kinetic Voronoi diagrams. We also show that the core of the star unfolding can overlap itself when the polyhedral surface is non-convex.

Description: Preemptive scheduling problems on parallel machines are classic problems. Given the goal of minimizing the makespan, they are polynomially solvable even for the most general model of unrelated machines. In these problems, a set of jobs is to be assigned to run on a set of m machines. A job can be split into parts arbitrarily and these parts are to be assigned to time slots on the machines without parallelism, that is, for every job, at most one of its parts can be processed at each time. Motivated by sensitivity analysis and online algorithms, we investigate the problem of designing robust algorithms for constructing preemptive schedules. Robust algorithms receive one piece of input at a time. They may change a small portion of the solution as an additional part of the input is revealed. The capacity of change is based on the size of the new piece of input. For scheduling problems, the supremum ratio between the total size of the jobs (or parts of jobs) which may be re-scheduled upon the arrival of a new job j , and the size of j , is called migration factor . We design a strongly optimal algorithm with the migration factor $1-\frac{1}{m}$ for identical machines. Strongly optimal algorithms avoid idle time and create solutions where the (non-increasingly) sorted vector of completion times of the machines is lexicographically minimal. In the case of identical machines this results not only in makespan minimization, but the created solution is also optimal with respect to any ℓ p norm (for p 〉1). We show that an algorithm of a smaller migration factor cannot be optimal with respect to makespan or any other ℓ p norm, thus the result is best possible in this sense as well. We further show that neither uniformly related machines nor identical machines with restricted assignment admit an optimal algorithm with a constant migration factor. This lower bound holds both for makespan minimization and for any ℓ p norm. Finally, we analyze the case of two machines and show that in this case it is still possible to maintain an optimal schedule with a small migration factor in the cases of two uniformly related machines and two identical machines with restricted assignment.

Description: We initiate the study of property testing of submodularity on the boolean hypercube. Submodular functions come up in a variety of applications in combinatorial optimization. For a vast range of algorithms, the existence of an oracle to a submodular function is assumed. But how does one check if this oracle indeed represents a submodular function? Consider a function f :{0,1} n →ℝ. The distance to submodularity is the minimum fraction of values of f that need to be modified to make f submodular. If this distance is more than ϵ 〉0, then we say that f is ϵ -far from being submodular. The aim is to have an efficient procedure that, given input f that is ϵ -far from being submodular, certifies that f is not submodular. We analyze a natural tester for this problem, and prove that it runs in subexponential time. This gives the first non-trivial tester for submodularity. On the other hand, we prove an interesting lower bound (that is, unfortunately, quite far from the upper bound) suggesting that this tester cannot be efficient in terms of ϵ . This involves non-trivial examples of functions which are far from submodular and yet do not exhibit too many local violations. We also provide some constructions indicating the difficulty in designing a tester for submodularity. We construct a partial function defined on exponentially many points that cannot be extended to a submodular function, but any strict subset of these values can be extended to a submodular function.

Description: Given an unlabeled, unweighted, and undirected graph with n vertices and small (but not necessarily constant) treewidth k , we consider the problem of preprocessing the graph to build space-efficient encodings (oracles) to perform various queries efficiently. We assume the word RAM model where the size of a word is Ω (log n ) bits. The first oracle, we present, is the navigation oracle which facilitates primitive navigation operations of adjacency, neighborhood, and degree queries. By way of an enumeration argument, which is of interest in its own right, we show the space requirement of the oracle is optimal to within lower order terms for all graphs with n vertices and treewidth k . The oracle supports the mentioned queries all in constant worst-case time. The second oracle, we present, is an exact distance oracle which facilitates distance queries between any pair of vertices (i.e., an all-pairs shortest-path oracle). The space requirement of the oracle is also optimal to within lower order terms. Moreover, the distance queries perform in O ( k 3 log 3 k ) time. Particularly, for the class of graphs of popular interest, graphs of bounded treewidth (where k is constant), the distances are reported in constant worst-case time.

Description: The framework of Bodlaender et al. (J Comput Sys Sci 75(8):423–434, 2009 ) and Fortnow and Santhanam (J Comput Sys Sci 77(1):91–106, 2011 ) allows us to exclude the existence of polynomial kernels for a range of problems under reasonable complexity-theoretical assumptions. However, some issues are not addressed by this framework, including the existence of Turing kernels such as the “kernelization” of leaf out - branching \((k)\) that outputs \(n\) instances each of size poly \((k)\) . Observing that Turing kernels are preserved by polynomial parametric transformations (PPTs), we define two kernelization hardness hierarchies by the PPT-closure of problems that seem fundamentally unlikely to admit efficient Turing kernelizations. This gives rise to the MK- and WK-hierarchies which are akin to the M- and W-hierarchies of parameterized complexity. We find that several previously considered problems are complete for the fundamental hardness class WK[1], including Min Ones   \(d\) -SAT \((k)\) , Binary NDTM Halting \((k)\) , Connected Vertex Cover \((k)\) , and Clique parameterized by  \(k \log n\) . We conjecture that no WK[1]-hard problem admits a polynomial Turing kernel. Our hierarchy subsumes an earlier hierarchy of Harnik and Naor that, from a parameterized perspective, is restricted to classical problems parameterized by witness size. Our results provide the first natural complete problems for, e.g., their class  \(VC_1\) ; this had been left open.

Description: We design a sublinear Fourier sampling algorithm for a case of sparse off-grid frequency recovery. These are signals with the form \(f(t) = \sum _{j=1}^k a_j \mathrm{e}^{i\omega _j t} + \int \nu (\omega )\mathrm{e}^{i\omega t}d\mu (\omega )\) ; i.e., exponential polynomials with a noise term. The frequencies \(\{\omega _j\}\) satisfy \(\omega _j\in [\eta ,2\pi -\eta ]\) and \(\min _{i\ne j} |\omega _i-\omega _j|\ge \eta \) for some \(\eta 〉 0\) . We design a sublinear time randomized algorithm which, for any \(\epsilon \in (0,\eta /k]\) , which takes \(O(k\log k\log (1/\epsilon )(\log k+\log (\Vert a\Vert _1/\Vert \nu \Vert _1))\) samples of \(f(t)\) and runs in time proportional to number of samples, recovering \(\omega _j'\approx \omega _j\) and \(a_j'\approx a_j\) such that, with probability \(\varOmega (1)\) , the approximation error satisfies \(|\omega _j'-\omega _j|\le \epsilon \) and \(|a_j-a_j'|\le \Vert \nu \Vert _1/k\) for all \(j\) with \(|a_j|\ge \Vert \nu \Vert _1/k\) . We apply our model and algorithm to bearing estimation or source localization and discuss their implications for receiver array processing.

Description: Self-stabilization is a versatile approach to fault-tolerance since it permits a distributed system to recover from any transient fault that arbitrarily corrupts the contents of all memories in the system. Byzantine tolerance is an attractive feature of distributed systems that permits to cope with arbitrary malicious behaviors. This paper focuses on systems that are both self-stabilizing and Byzantine tolerant. Combining these two properties is known to induce many impossibility results. Hence, there exist several fault tolerance schemes to contain Byzantine faults in self-stabilization. In this paper, we consider the well known problem of constructing a maximum metric tree in this context. We provide a new distributed protocol that ensures the best possible containment with respect to topology-aware strict and strong stabilization.

Description: The Integer Programming Problem (IP) for a polytope \(P \subseteq \mathbb{R} ^{n}\) is to find an integer point in P or decide that P is integer free. We give a randomized algorithm for an approximate version of this problem, which correctly decides whether P contains an integer point or whether a (1+ ϵ )-scaling of P about its center of gravity is integer free in 2 O ( n ) (1/ ϵ 2 ) n -time and 2 O ( n ) (1/ ϵ ) n -space with overwhelming probability. Our algorithm proceeds by reducing the approximate IP problem to an approximate Closest Vector Problem (CVP) under a “near-symmetric” norm. Our main technical contribution is an extension of the AKS randomized sieving technique, first developed by Ajtai et al. (Proceedings of 33rd Symposium on the Theory of Computing (STOC), pp. 601–610, 2001 ) for lattice problems under the ℓ 2 norm, to the setting of asymmetric norms. We also present an application of our techniques to exact IP, where we give a nearly optimal algorithmic implementation of the Flatness Theorem, a central ingredient for many IP algorithms. Our results also extend to general convex bodies and lattices.