Search

Intersection graphs are well-studied in the area of graph algorithms. Some intersection graph classes are known to have algorithms enumerating all unlabeled graphs by reverse search. Since these algorithms output graphs one by one and the numbers of graphs in these classes are vast, they work only for a small number of vertices. Binary decision diagrams (BDDs) are compact data structures for various types of data and useful for solving optimization and enumeration problems. This study proposes enumeration algorithms for five intersection graph classes, which admit O (n) -bit string representations for their member graphs. Our algorithm for each class enumerates all unlabeled graphs with n vertices over BDDs representing the binary strings in time polynomial in n. Moreover, our algorithms are extended so that it enumerates those with constraints on the maximum (bi)clique size and/or the number of edges. [ABSTRACT FROM AUTHOR]

Various forms of sorting problems have been studied over the years. Recently, two kinds of sorting puzzle apps have gained popularity. In these puzzles, we are given a set of bins filled with colored units, balls or water, and some empty bins. These puzzles allow us to move colored units from a bin to another when the colors involved match in some way or the target bin is empty. The goal of these puzzles is to sort all the color units in order. We investigate computational complexities of these puzzles. We first show that these two puzzles are essentially the same from the viewpoint of solvability. That is, an instance is sortable by ball-moves if and only if it is sortable by water-moves. We also show that every yes-instance has a solution of polynomial length, which implies that these puzzles belong to NP. We then show that these puzzles are NP-complete. For some special cases, we give polynomial-time algorithms. We finally consider the number of empty bins sufficient for making all instances solvable and give non-trivial upper and lower bounds in terms of the number of filled bins and the capacity of bins. [ABSTRACT FROM AUTHOR]

We consider a variant of the online buffer management problem in network switches, called the k -frame throughput maximization problem ( k -FTM). This problem models the situation where a large frame is fragmented into k packets and transmitted through the Internet, and the receiver can reconstruct the frame only if he/she accepts all the k packets. Kesselman et al. introduced this problem and showed that its competitive ratio is unbounded even when k = 2 . They also introduced an “order-respecting” variant of k -FTM, called k -OFTM, where inputs are restricted in some natural way. They proposed an online algorithm and showed that its competitive ratio is at most 2 k B ⌊ B / k ⌋ + k for any B ≥ k , where B is the size of the buffer. They also gave a lower bound of B ⌊ 2 B / k ⌋ for deterministic online algorithms when 2 B ≥ k and k is a power of 2. In this paper, we improve upper and lower bounds on the competitive ratio of k -OFTM. Our main result is to improve an upper bound of O ( k 2 ) by Kesselman et al. to 5 B + ⌊ B / k ⌋ − 4 ⌊ B / 2 k ⌋ = O ( k ) for B ≥ 2 k . Note that this upper bound is tight up to a multiplicative constant factor since the lower bound given by Kesselman et al. is Ω ( k ) . We also give two lower bounds. First we give a lower bound of 2 B ⌊ B / ( k − 1 ) ⌋ + 1 on the competitive ratio of deterministic online algorithms for any k ≥ 2 and any B ≥ k − 1 , which improves the previous lower bound of B ⌊ 2 B / k ⌋ by a factor of almost four. Next, we present the first nontrivial lower bound on the competitive ratio of randomized algorithms. Specifically, we give a lower bound of k − 1 against an oblivious adversary for any k ≥ 3 and any B . Since a deterministic algorithm, as mentioned above, achieves an upper bound of about 10 k , this indicates that randomization does not help too much. [ABSTRACT FROM AUTHOR]

We consider the one-dimensional version of the online unit clustering problem, proposed by Chan and Zarrabi-Zadeh (WAOA2007 and Theory of Computing Systems 45(3), 2009), which is defined as follows: “Points” are given online on the line one by one. An algorithm creates a “cluster,” which is a line segment. The initial length of a cluster is 0, and an algorithm can extend a cluster until it reaches unit length. The task of an algorithm is to cover a new given point either by creating a new cluster and assigning the point to the cluster or by extending an existing cluster created in past times. The goal is to minimize the total number of created clusters. In this paper, we show a lower bound of 13 / 8 = 1.625 on the competitive ratio of any deterministic online algorithm for the one-dimensional unit clustering, improving the previous lower bound 8 / 5 ( = 1.6 ) presented by Epstein and van Stee (WAOA2007 and ACM Transactions on Algorithms 7(1), 2010). Note that Ehmsen and Larsen (SWAT2010 and Theoretical Computer Science, 500, 2013) showed the current best upper bound of 5/3. [ABSTRACT FROM AUTHOR]

Abstract: It has been a long-standing open problem to determine the exact randomized competitiveness of the -server problem, that is, the minimum competitiveness of any randomized online algorithm for the -server problem. For deterministic algorithms the best competitive ratio that can be obtained is and no randomized algorithm is known that improves this ratio for general spaces. For the line, Bartal et al. (1998)  give a competitive algorithm, but their algorithm is specific to the geometry of the line. We consider here the -server problem over Cross Polytope Spaces . We obtain an algorithm with competitive ratio of , and show that this ratio is best possible. This algorithm gives the second non-trivial example of metric spaces with better than-competitive ratio. The algorithm uses a design technique called the knowledge state technique — a method not specific to . [ABSTRACT FROM AUTHOR]

Consider a puzzle consisting of n tokens on an n -vertex graph, where each token has a distinct starting vertex and a distinct target vertex it wants to reach, and the only allowed transformation is to swap the tokens on adjacent vertices. We prove that every such puzzle is solvable in O ( n 2 ) token swaps, and thus focus on the problem of minimizing the number of token swaps to reach the target token placement. We give a polynomial-time 2-approximation algorithm for trees, and using this, obtain a polynomial-time 2 α -approximation algorithm for graphs whose tree α -spanners can be computed in polynomial time. Finally, we show that the problem can be solved exactly in polynomial time on complete bipartite graphs. [ABSTRACT FROM AUTHOR]