waashk/dblp huggingface dataset:
information measures for infinite sequences. we revisit the notion of computational depth and sophistication for infinite sequences and study the density of the sets of deep and sophisticated infinite sequences. koppel defined the sophistication of an object as the length of the shortest total program that, given some data as input, produces the object and such that the sum of the size of the program with the size of the data is as concise as the smallest description of the object. however, the notion of sophistication is not properly defined for all sequences. we propose a new definition of sophistication for infinite sequences as the limit of the ratio of the sophistication of the initial segments and its length. we prove that the set of sequences with sophistication equal to zero has lebesgue measure one and that the set of sophisticated sequences is dense, when the sophistication is, respectively, defined either using lim inf or lim sup. antunes, fortnow, van melkebeek and vinodchandran captured the notion of useful information by computational depth, the difference between time bounded and unbounded kolmogorov complexities. we show that the set of deep infinite sequences is dense. we also prove that sophistication and depth for infinite sequences are distinct information measures.
theoretical underpinnings for maximal clique enumeration on perturbed graphs. the problem of enumerating the maximal cliques of a graph is a computationally expensive problem with applications in a number of different domains. sometimes the benefit of knowing the maximal clique enumeration (mce) of a single graph is worth investing the initial computation time. however, when graphs are abstractions of noisy or uncertain data, the mce of several closely related graphs may need to be found, and the computational cost of doing so becomes prohibitively expensive. here, we present a method by which the cost of enumerating the set of maximal cliques for related graphs can be reduced. by using the mce for some baseline graph, the mce for a modified, or perturbed, graph may be obtained by enumerating only the maximal cliques that are created or destroyed by the perturbation. when the baseline and perturbed graphs are relatively similar, the difference set between the two mces can be overshadowed by the maximal cliques common to both. thus, by enumerating only the difference set between the baseline and perturbed graphs' mces, the computational cost of enumerating the maximal cliques of the perturbed graph can be reduced. we present necessary and sufficient conditions for enumerating difference sets when the perturbed graph is formed by several different types of perturbations. we also present results of an algorithm based on these conditions that demonstrate a speedup over traditional calculations of the mce of perturbed, real biological networks.
randomized priority algorithms. borodin, nielsen and rackoff [13] introduced the class of priority algorithms as a framework for modeling deterministic greedy-like algorithms. in this paper we address the effect of randomization in greedy-like algorithms. more specifically, we consider approximation ratios within the context of randomized priority algorithms. as case studies, we prove inapproximation results for two well-studied optimization problems, namely facility location and makespan scheduling.
tight results for next fit and worst fit with resource augmentation. it is well known that the two simple algorithms for the classic bin packing problem, nf and wf both have an approximation ratio of 2. however, wf seems to be a more reasonable algorithm, since it never opens a new bin if an existing bin can still be used. using resource augmented analysis, where the output of an approximation algorithm, which can use bins of size b>1, is compared to an optimal packing into bins of size 1, we give a complete analysis of the asymptotic approximation ratio of wf and of nf, and use it to show that wf is strictly better than nf for any 1=2, and for b=1.
inapproximability results for equations over infinite groups. an equation over a group g is an expression of form w"1...w"k=1"g, where each w"i is either a variable, an inverted variable, or a group constant and 1"g denotes the identity element; such an equation is satisfiable if there is a setting of the variables to values in g such that the equality is realized (engebretsen et al. (2002) [10]). in this paper, we study the problem of simultaneously satisfying a family of equations over an infinite group g. let eq"g[k] denote the problem of determining the maximum number of simultaneously satisfiable equations in which each equation has occurrences of exactly k different variables. when g is an infinite cyclic group, we show that it is np-hard to approximate eq^1"g[3] to within 48/47-@e, where eq^1"g[3] denotes the special case of eq"g[3] in which a variable may only appear once in each equation; it is np-hard to approximate eq^1"g[2] to within 30/29-@e; it is np-hard to approximate the maximum number of simultaneously satisfiable equations of degree at most d to within d-@e for any @e; for any k>=4, it is np-hard to approximate eq"g[k] within any constant factor. these results extend hastad's results (hastad (2001) [17]) and results of (engebretsen et al. (2002) [10]), who established the inapproximability results for equations over finite abelian groups and any finite groups respectively.
a class of hierarchical graphs as topologies for interconnection networks. we study some topological and algorithmic properties of a recently defined hierarchical interconnection network, the hierarchical crossed cube hcc(k,n), which draws upon constructions used within the well-known hypercube and also the crossed cube. in particular, we study: the construction of shortest paths between arbitrary vertices in hcc(k,n); the connectivity of hcc(k,n); and one-to-all broadcasts in parallel machines whose underlying topology is hcc(k,n) (with both one-port and multi-port store-and-forward models of communication). moreover, some of our proofs are applicable not just to hierarchical crossed cubes but to hierarchical interconnection networks formed by replacing crossed cubes with other families of interconnection networks. as such, we provide a generic construction with accompanying generic results relating to some topological and algorithmic properties of a wide range of hierarchical interconnection networks
dykstra's algorithm for constrained least-squares doubly symmetric matrix problems. in this work we apply dykstra's alternating projection algorithm for minimizing @?ax-b@? where @?@?@? is the frobenius norm and a@?r^m^x^n, b@?r^m^x^n and x@?r^n^x^n are doubly symmetric positive definite matrices with entries within prescribed intervals. we first solve the constrained least-squares matrix problem by using the special structure properties of doubly symmetric matrices, and then use the singular value decomposition to transform the original problem into a simpler one that fits nicely with the algorithm originally developed by [r. escalante, m. raydan, dykstra's algorithm for a constrained least-squares matrix problem, numer. linear algebra appl. 3 (1996) 459-471].
exact leaf powers. we define and study the new notion of exact k-leaf powers where a graph g=(v"g,e"g) is an exact k-leaf power if and only if there exists a tree t=(v"t,e"t) - an exact k-leaf root of g - whose set of leaves equals v"g such that uv@?e"g holds for u,v@?v"g if and only if the distance of u and v in t is exactly k. this new notion is closely related to but different from leaf powers and neighbourhood subtree tolerance graphs. we prove characterizations of exact 3- and 4-leaf powers which imply that such graphs can be recognized in linear time and that also the corresponding exact leaf roots can be found in linear time. furthermore, we characterize all exact 5-leaf roots of chordless cycles and derive several properties of exact 5-leaf powers.
an optimal algorithm to generate rooted trivalent diagrams and rooted triangular maps. a trivalent diagram is a connected, two-colored bipartite graph (parallel edges allowed but not loops) such that every black vertex is of degree 1 or 3 and every white vertex is of degree 1 or 2, with a cyclic order imposed on every set of edges incident to the same vertex. a rooted trivalent diagram is a trivalent diagram with a distinguished edge, its root. we shall describe and analyze an algorithm giving an exhaustive list of rooted trivalent diagrams of a given size (number of edges), the list being non-redundant in that no two diagrams of the list are isomorphic. the algorithm will be shown to have optimal performance in that the time necessary to generate a diagram will be seen to be bounded in the amortized sense, the bound being independent of the size of the diagrams. we call this the cat property. one objective of the paper is to provide a reusable theoretical framework for algorithms generating exhaustive lists of complex combinatorial structures with attention paid to the case of unlabeled structures and to those generators having the cat property.
two-dimensional online bin packing with rotation. in two-dimensional bin packing problems, the input items are rectangles which need to be packed in a non-overlapping manner. the goal is to assign the items into unit squares using an axis-parallel packing. most previous work on online packing concentrated on items of fixed orientation, which must be assigned such that their bottom side is parallel to the bottom of the bin. in this paper we study the case of rotatable items, which can be rotated by ninety degrees. we give almost tight bounds on the (asymptotic) competitive ratio of bounded space bin packing of rotatable items, and introduce a new unbounded space algorithm. this improves the results of fujita and hada.
approximability and inapproximability of the minimum certificate dispersal problem. given an n-vertex directed graph g=(v,e) and a set r@?vxv of requests, we consider assigning a set of edges to each vertex in g so that for every request (u,v) in r the union of the edge sets assigned to u and v contains a path from u to v. the minimum certificate dispersal problem (mcd) is defined as one to find an assignment that minimizes the sum of the cardinalities of the edge sets assigned to each vertex. this problem has been shown to be np-hard in general, though it is polynomially solvable for some restricted classes of graphs and restricted request structures, such as bidirectional trees with requests of all pairs of vertices. in this paper, we give an advanced investigation about the difficulty of mcd by focusing on the relationship between its (in)approximability and request structures. we first show that mcd with general r has @q(logn) lower and upper bounds on approximation ratio under the assumption p
the bridge-connectivity augmentation problem with a partition constraint. in this paper, we consider the augmentation problem of an undirected graph with k partitions of its vertices. the main issue is how to add a set of edges with the smallest possible cardinality so that the resulting graph is 2-edge-connected, i.e., bridge-connected, while maintaining the original partition constraint. to solve the problem, we propose a simple linear-time algorithm. to the best of our knowledge, the most efficient sequential algorithm runs in o(n(m+nlogn)logn) time. however, we show that it can also run in o(logn) parallel time on an erew pram using a linear number of processors, where n is the number of vertices in the input graph. if a simple graph exists, our main algorithm ensures that it is as simple as possible.
efficient frequent connected subgraph mining in graphs of bounded tree-width. the frequent connected subgraph mining problem, i.e., the problem of listing all connected graphs that are subgraph isomorphic to at least a certain number of transaction graphs of a database, cannot be solved in output polynomial time in the general case. if, however, the transaction graphs are restricted to forests then the problem becomes tractable. in this paper we generalize the positive result on forests to graphs of bounded tree-width. in particular, we show that for this class of transaction graphs, frequent connected subgraphs can be listed in incremental polynomial time. since subgraph isomorphism remains np-complete for bounded tree-width graphs, the positive complexity result of this paper shows that efficient frequent pattern mining is possible even for computationally hard pattern matching operators.
factors of characteristic words: location and decompositions. let @a be an irrational number with 0
deterministic on-line call control in cellular networks. we study an on-line call control problem in cellular networks that are based on the frequency division multiplexing (fdm) technology. in such networks, interference may occur when the same frequency is assigned to two different calls emanating from the same cell or its neighboring cells. the number of frequencies supporting the networks is limited. the goal is to maximize the number of calls served without causing any interference. we focus on the case that the number of frequencies is sufficiently large and the calls stay forever. we give a deterministic on-line algorithm with asymptotic competitive ratio of 2.5 and show a general lower bound of 2. for the special case of linear cellular networks, we achieve a best possible deterministic on-line algorithm with asymptotic competitive ratio of 3/2.
window-games between tcp flows. we consider network congestion problems between tcp flows and define a new game, the window-game, which models the problems of network congestion caused by the competing flows. analytical and experimental results show the relevance of the window-game to real tcp congestion games and provide interesting insight into the respective nash equilibria. furthermore, we propose a new algorithmic queue mechanism, called prince, which at congestion makes a scapegoat of the most greedy flow. we provide evidence which shows that prince achieves efficient nash equilibria while requiring only limited computational resources.
online scheduling with reassignment on two uniform machines. in this paper, we investigate the online scheduling problem on two uniform machines, where the last job of each machine can be reassigned after all jobs have been assigned. the objective is to minimize the makespan. we prove that the classical list scheduling algorithm with the competitive ratio s+1s is optimal for s>=1+52, where s is the speed ratio between the two machines. also, we prove the lower bound s+1 for 1@?s
an upper bound for the circuit complexity of existentially quantified boolean formulas. the expressive power of existentially quantified boolean formulas @?cnf with free variables is investigated. we introduce a hierarchy of subclasses @?mu^*(k) of @?cnf formulas based on the maximum deficiency k of minimal unsatisfiable subformulas of the bound part of the formulas. we will establish an upper bound of the size of minimally equivalent circuits. it will be shown, that there are constants a and b, such that for every formula in @?mu^*(k) of length m of the bound part and length l of the free part of the formula there is an equivalent circuit of size less than l+a@?m^b^(^l^o^g^"^2^(^m^)^+^k^)^^^2.
a compact fixpoint semantics for term rewriting systems. this work is motivated by the fact that a ''compact'' semantics for term rewriting systems, which is essential for the development of effective semantics-based program manipulation tools (e.g. automatic program analyzers and debuggers), does not exist. the big-step rewriting semantics that is most commonly considered in functional programming is the set of values/normal forms that the program is able to compute for any input expression. such a big-step semantics is unnecessarily oversized, as it contains many ''semantically useless'' elements that can be retrieved from a smaller set of terms. therefore, in this article, we present a compressed, goal-independent collecting fixpoint semantics that contains the smallest set of terms that are sufficient to describe, by semantic closure, all possible rewritings. we prove soundness and completeness under ascertained conditions. the compactness of the semantics makes it suitable for applications. actually, our semantics can be finite whereas the big-step semantics is generally not, and even when both semantics are infinite, the fixpoint computation of our semantics produces fewer elements at each step. to support this claim we report several experiments performed with a prototypical implementation.
a polynomial-time algorithm for the weighted link ring loading problem with integer demand splitting. we are given an n-node undirected ring network, in which each link of the ring is associated with a weight. traffic demand is given for each pair of nodes in the ring. each demand is allowed to be split into two integer parts, which are then routed in different directions, clockwise and counterclockwise, respectively. the load of a link is the sum of the flows routed through the link and the nonnegative weighted load of a link is the product of its weight and its load. the objective is to find a routing scheme such that the maximum weighted load on the ring is minimized. based on some useful structural properties of the decision version of the problem, we design a polynomial-time combinatorial algorithm for the optimization problem.
left-forbidding cooperating distributed grammar systems. a left-forbidding grammar, introduced in this paper, is a context-free grammar, where a set of nonterminal symbols is attached to each context-free production. such a production can rewrite a nonterminal provided that no symbol from the attached set occurs to the left of the rewritten nonterminal in the current sentential form. the present paper discusses cooperating distributed grammar systems with left-forbidding grammars as components and gives some new characterizations of language families of the chomsky hierarchy. in addition, it also proves that twelve nonterminals are enough for cooperating distributed grammar systems working in the terminal derivation mode with two left-forbidding components (including erasing productions) to characterize the family of recursively enumerable languages.
the surviving rate of an infected network. let g be a connected network. let k>=1 be an integer. suppose that a vertex v of g becomes infected. a program is then installed on k-nodes not yet infected. afterwards, the virus spreads to all its unprotected neighbors in each time interval. the virus and the network administrator take turns until the virus can no longer spread further. let sn"k(v) denote the maximum number of vertices in g the network administrator can save when a virus infects v. the k-surviving rate @r"k(g) of g is defined to be the average value @?"v"@?"v"("g")sn"k(v)/n^2. in particular, we write @r(g)=@r"1(g). in this paper, we first use a probabilistic method to show that almost all networks have k-surviving rate arbitrarily close to 0. then, we prove the following results: (1) @r(g)>=235 for a planar network g of girth at least 9; (2) @r"2(g)>=116 for a series-parallel network g; and (3) @r"""2"""d"""-"""1(g)>=25d for a d-degenerate network g.
acyclic automata and small expressions using multi-tilde-bar operators. a regular expression with n occurrences of symbol can be converted into an equivalent automaton with (n+1) states, the so-called glushkov automaton of the expression. conversely, it is possible to decide whether a given (n+1)-state automaton is a glushkov one and, if so, to convert it back to an equivalent regular expression of width n. our goal is to extend the class of automata for which such a linear retranslation is possible. we define new regular operators, called multi-tilde-bars, allowing us to simultaneously apply a multi-tilde operator and a multi-bar one to a list of expressions. the main results are that a multi-tilde-bar expression of width n can be converted into an (n+1)-state position-like automaton and that any acyclic n-state automaton can be turned into an extended expression of width o(n).
the college admissions problem with lower and common quotas. we study two generalised stable matching problems motivated by the current matching scheme used in the higher education sector in hungary. the first problem is an extension of the college admissions problem in which the colleges have lower quotas as well as the normal upper quotas. here, we show that a stable matching may not exist and we prove that the problem of determining whether one does is np-complete in general. the second problem is a different extension in which, as usual, individual colleges have upper quotas, but, in addition, certain bounded subsets of colleges have common quotas smaller than the sum of their individual quotas. again, we show that a stable matching may not exist and the related decision problem is np-complete. on the other hand, we prove that, when the bounded sets form a nested set system, a stable matching can be found by generalising, in non-trivial ways, both the applicant-oriented and college-oriented versions of the classical gale-shapley algorithm. finally, we present an alternative view of this nested case using the concept of choice functions, and with the aid of a matroid model we establish some interesting structural results for this case.
reconstructing hv-convex multi-coloured polyominoes. in this paper, we consider the problem of reconstructing polyominoes from information about the thickness in vertical and horizontal directions. we focus on the case where there are multiple disjoint polyominoes (of different colours) that are hv-convex, i.e., any intersection with a horizontal or vertical line is contiguous. we show that reconstruction of such polyominoes is polynomial if the number of colours is constant, but np-hard for an unbounded number of colours.
checking experiments for stream x-machines. stream x-machines are a state based formalism that has associated with it a particular development process in which a system is built from trusted components. testing thus essentially checks that these components have been combined in a correct manner and that the orders in which they can occur are consistent with the specification. importantly, there are test generation methods that return a checking experiment: a test that is guaranteed to determine correctness as long as the implementation under test (iut) is functionally equivalent to an unknown element of a given fault domain @j. previous work has show how three methods for generating checking experiments from a finite state machine (fsm) can be adapted to testing from a stream x-machine. however, there are many other methods for generating checking experiments from an fsm and these have a variety of benefits that correspond to different testing scenarios. this paper shows how any method for generating a checking experiment from an fsm can be adapted to generate a checking experiment for testing an implementation against a stream x-machine. this is the case whether we are testing to check that the iut is functionally equivalent to a specification or we are testing to check that every trace (input/output sequence) of the iut is also a trace of a nondeterministic specification. interestingly, this holds even if the fault domain @j used is not that traditionally associated with testing from a stream x-machine. the results also apply for both deterministic and nondeterministic implementations.
algorithm for two disjoint long paths in 2-connected graphs. in this paper, we prove that 2-connected graphs have either a dominating path or two disjoint paths, wherein the length of the two paths is bounded by the minimum among n and a parameter defined on the neighborhood condition of any four independent vertices of the graph.