waashk/dblp huggingface dataset:
linear tolls suffice: new bounds and algorithms for tolls in single source networks. we show that tolls that are linear in the latency of the maximum latency path are necessary and sufficient to induce heterogeneous network users to independently choose routes that lead to traffic with minimum average latency. this improves upon the earlier bound of o(n3lmax) given by cole, dodis, and roughgarden in stoc 03. (here, n is the number of nodes in the network; and lmax is the maximum latency of any edge.) our proof is also simpler, relating the nash flow to the optimal flow as flows rather than cuts.we model the set of users as the set [0, 1] ordered by their increasing willingness to pay tolls to reduce latency--their valuation of time. cole et al. give an algorithm that computes optimal tolls for a bounded number of agent valuations, under the very strong assumption that they know which path each user type takes in the nash flow imposed by these (unknown) tolls. we show that in series parallel graphs, the set of paths traveled by users in any nash flow with optimal tolls is independent of the distribution of valuations of time of the users. in particular, for any continuum of users (not restricted to a finite number of valuation classes) in series parallel graphs, we show how to compute these paths without knowing α.we give a simple example to demonstrate that if the graph is not series parallel, then the set of paths traveled by users in the nash flow depends critically on the distribution of users' valuations of time.
domains in h. we give various internal descriptions of the category &ohgr;-cpo of &ohgr;-complete posets and &ohgr;-continuous functions in the model h of synthetic domain theory introduced in fiore and rosolini (j. pure appl. algebra 116 (1997) 151-162). it follows that the &ohgr;-cpos lie between the two extreme synthetic notions of domain given by repleteness and well-completeness.
combining word problems through rewriting in categories with products. we give an algorithm solving combined word problems (over non-necessarily disjoint signatures) based on rewriting of equivalence classes of terms. the canonical rewriting system we introduce consists of few transparent rules and is obtained by applying knuth-bendix completion procedure to presentations of pushouts among categories with products. it applies to pairs of theories which are both constructible over their common reduct (on which we do not make any special assumption).
cellular automata and strongly irreducible shifts of finite type. if a is a finite alphabet and γ is a finitely generated amenable group, ceccherini-silberstein, machì and scarabotti have proved that a local transition function defined on the full shift aγ is surjective if and only if it is pre-injective; this equivalence is the so-called garden of eden theorem. on the other hand, when γ is the group of the integers, the theorem holds in the case of irreducible shifts of finite type as a consequence of a theorem of lind and marcus but it no longer holds in the two-dimensional case.recently, gromov has proved a goe-like theorem in the much more general framework of the spaces of bounded propagation. in this paper we apply gromov's theorem to our class of spaces proving that all the properties required in the hypotheses of this theorem are satisfied.we give a definition of strong irreducibility that, together with the finite-type condition, it allows us to prove the goe theorem for the strongly irreducible shifts of finite type in aγ (provided that γ is amenable). finally, we prove that the bounded propagation property for a shift is strictly stronger than the union of strong irreducibility and finite-type condition.
the directed subgraph homeomorphism problem. the set of pattern graphs for which the directed subgraph homeomorphism problem is np-complete is characterized. a polynomial time algorithm is given for the remaining cases. the restricted problem where the input graph is a directed acyclic graph is in polynomial time for all pattern graphs and an algorithm is given.
semiretracts--a counterexample and some results. in the paper (theoret. comput. sci. 237 (2000)) anderson present a theorem which characterizes any semiretract s by means of two retracts rα and rω. the first part of the paper contains a counterexample for this characterization. then some results are presented which finally lead to the theorem which determines for a given semiretract s the minimal number of retracts r1,...,rm such that the equality s = ∩i=1m ri holds.
incremental algorithms for facility location and -median. in the incremental versions of facility location and k-median, the demand points arrive one at a time and the algorithm maintains a good solution by either adding each new demand to an existing cluster or placing it in a new singleton cluster. the algorithm can also merge some of the existing clusters at any point in time.for facility location, we consider the case of uniform facility costs, where the cost of opening a facility is the same for all points, and present the first incremental algorithm which achieves a constant performance ratio. using this algorithm as a building block, we obtain the first incremental algorithm for k-median which achieves a constant performance ratio using o(k) medians.the algorithm is based on a novel merge rule which ensures that the algorithm's configuration monotonically converges to the optimal facility locations according to a certain notion of distance. using this property, we reduce the general case to the special case when the optimal solution consists of a single facility.
selfish unsplittable flows. what is the price of anarchy when unsplittable demands are routed selfishly in general networks with load-dependent edge delays? motivated by this question we generalize the model of koutsoupias and papadimitriou (worst-case equilibria, in: proc. of the 16th annual symp. on theoretical aspects of computer science (stacs '99), lecture notes in computer science, vol. 1563, springer, berlin, 1999, pp. 404-413) to the case of weighted congestion games. we show that varying demands of users crucially affect the nature of these games, which are no longer isomorphic to exact potential games, even for very simple instances. indeed we construct examples where even a single-commodity (weighted) network congestion game may have no pure nash equilibrium.on the other hand, we prove that any weighted network congestion game with linear edge delays admits a pure nash equilibrium that can be found in pseudo-polynomial time. finally, we consider the family of l-layered networks and give a surprising answer to the question above: the price of anarchy of any weighted congestion game in a l-layered network with m edges and edge delays equal to the loads is θ(log m/log log m).
radiocoloring in planar graphs: complexity and approximations. the frequency assignment problem (fap) in radio networks is the problem of assigning frequencies to transmitters, by exploiting frequency reuse while keeping signal interference to acceptable levels. the fap is usually modelled by variations of the graph coloring problem. a radiocoloring (rc) of a graph g(v, e) is an assignment function φ : v → n such that |φ(u) - φ(v) | ≥ 2, when u, v are neighbors in g, and |φ(u) - φ(v)| ≥ 1 when the distance of u, v in g is two. the number of discrete frequencies and the range of frequencies used are called order and span, respectively. the optimization versions of the radiocoloring problem (rcp) are to minimize the span or the order. in this paper we prove that the radiocoloring problem for general graphs is hard to approximate (unless np = zpp) within a factor of n1/2-ε (for any ε > 0), where n is the number of vertices of the graph. however, when restricted to some special cases of graphs, the problem becomes easier. we prove that the min span rcp is np-complete for planar graphs. next, we provide an o(nδ) time algorithm (|v| = n) which obtains a radiocoloring of a planar graph g that approximates the minimum order within a ratio which tends to 2 (where δ the maximum degree of g). finally, we provide a fully polynomial randomized approximation scheme (fpras) for the number of valid radiocolorings of a planar graph g with λ colors, in the case where λ ≥ 4δ + 50.
the one-dimensional ising model: mutation versus recombination. the investigation of genetic and evolutionary algorithms on ising model problems gives much insight into how these algorithms work as adaptation schemes. the one-dimensional ising model with periodic boundary conditions has been considered as a typical example with a clear building block structure suited well for two-point crossover. it has been claimed that gas based on recombination and appropriate diversity-preserving methods by far outperform eas based on mutation only. here, a rigorous analysis of the expected optimization time proves that mutation-based eas are surprisingly effective. the (1 +λ) ea with an appropriate λ-value is almost as efficient as typical gas. moreover, it is proved that specialized gas do even better and this holds for two-point crossover as well as for one-point crossover.
intersection number and topology preservation within digital surfaces. in this paper, we prove a new result of digital topology which states that the digital fundamental groupa notion previously introduced by kong (comput. graphics 13 (1989) 159-166)is sufficient to characterize topology preservation within digital surfaces. this proof involves a new tool for proving theorems in this field: the intersection number which counts the number of real intersections between two surfels loops lying on a digital surface. the main property of the intersection number and the reason why it is useful is the following: the intersection number between two paths does not change after any continuous deformation applied to the paths.
cryptographic limitations on parallelizing membership and equivalence queries with applications to random-self-reductions. we assume wlog that every learning algorithm with membership and equivalence queries proceeds in rounds. in each round it puts in parallel a polynomial number of queries and after receiving the answers, it performs internal computations before starting the next round. the query depth is defined by the number of rounds. in this paper we show that, assuming the existence of cryptographic one-way functions, for any fixed polynomial d(n) there exists a concept class that is efficiently and exactly learnable with membership queries in query depth d(n)+1, but cannot be weakly predicted with membership and equivalence queries in depth d(n). hence, concerning the query depth, efficient learning algorithms for this concept class cannot be parallelized. we also discuss applications to random-self-reductions and coherent sets. copyright 2001 elsevier science b.v. all rights reserved.
bisimulations in the join-calculus. we develop a theory of bisimulations in the join-calculus. we introduce a refined operational model that makes interactions with the environment explicit, and discuss the impact of the lexical scope discipline of the join-calculus on its extensional semantics. we propose several formulations of bisimulation and establish that all formulations yield the same equivalence. we prove that this equivalence is finer than barbed congruence, but that both relations coincide in the presence of name matching. copyright 2001 elsevier science b.v.
on maximizing the throughput of multiprocessor tasks. we consider the problem of scheduling n independent multiprocessor tasks with due dates and unit processing times, where the objective is to compute a schedule maximizing the throughput. we derive the complexity results and present several approximation algorithms. for the parallel variant of the problem, we introduce the first-fit increasing algorithm and the latest-fit increasing algorithm, and prove that their worst-case ratios are 2 and 2 - 1/m, respectively (m ≥ 2 is the number of processors). then we propose a revised algorithm with a worst-case ratio bounded by 3/2- 1/(2m) (m is odd) and 3/2-1/(2m-2) (m is even). for the dedicated variant, we present a simple greedy algorithm. we show that its worst-case ratio is bounded by √m + 1. we straighten this result by showing that the problem cannot be approximated within a factor of m1/2-ε for any ε > 0, unless np = zpp.
combinatorics of perfect matchings in plane bipartite graphs and application to tilings. let g be a plane bipartite graph which admits a perfect matching and with distinguished faces called holes. let mg denote the perfect matchings graph: its vertices are the perfect matchings of g, two of them being joined by an edge, if and only if they differ only on an alternating cycle bounding a face which is not a hole. we solve the following problem: find a criterion for two perfect matchings of g to belong to the same connected component of mg and in particular determine in which case mg is connected. the motivation of this work is a result on tilings of saldanha et al. (comput. geom. 14 (1995) 207).
a weakly mixing tiling dynamical system with a smooth model. we describe a weakly mixing one-dimensional tiling dynamical system in which the tiling space is modeled by a surface m of genus 2. the tiling system satisfies an inflation, and the inflation map is modeled by a pseudo-anosov diffeomorphism d on m. the expansion coefficient θ for d is a non-pisot number. in particular, the leaves of the expanding foliation for d are tiled by their visits to the elements of a markov partition for d. the tiling dynamical system is an almost 1:1 extension of the unit speed flow along these leaves.
arrays, numeration systems and frankenstein games. we define an infinite array a of nonnegative integers based on a linear recurrence, whose second row provides basis elements of an exotic ternary numeration system. using the numeration system we explore many properties of a. further, we propose and analyze a family frankenstein of 2-player pebbling games played on a semi-infinite strip, and present a winning strategy based on certain subarrays of a. though the strategy looks easy, it is actually computationally hard. the numeration system is then used to decide whether the family has an efficient strategy or not.
complexity, appeal and challenges of combinatorial games. studying the precise nature of the complexity of games enables gamesters to attain a deeper understanding of the difficulties involved in certain new and old open game problems, which is a key to their solution. for algorithmicians, such studies provide new interesting algorithmic challenges, substantiations of these assertions are illustrated on hand of many sample games, leading to a definition of the tractability, polynomiality and efficiency of subsets of games. in particular, there are tractable games that need not be polynomial, polynomial games that need not be efficient. we also define and explore the nature of the subclasses playgames and mathgames.
the essence of ideal completion in quantitative form. if a poset lacks joins of directed subsets, one can pass to its ideal completion. but doing this means also changing the setting: the universal property of ideal completion of posets suggests that it should be regarded as a functor from the category of posets with monotone maps to the category of dcpos with scott-continuous functions as morphisms. the same applies for the quantitative version of ideal completion suggested in the literature. as in the case of posets, it seems advantageous to consider a different topology with the completed spaces. we introduce topological v-continuity spaces and their smyth completion and show that this is an adequate setting to consider ideal completion of quantitative domains: performing the smyth completion of a v-continuity space regarded as topological v-continuity space gives the ideal completion of the original space together with its scott topology.
adjoining to wythoff's game its -positions as moves. a rewarding method for generating a new game g>sub<i+1>/sub< from a known game g>sub/sub< is to adjoin an appropriate subset of the p-positions (2nd player winning positions) of g>sub/sub< to g>sub<i+1>/sub< as moves. we illustrate this statement by adjoining to the generalized wythoff game three subsets of its p-positions as moves, resulting in three different classes of games. we analyze these classes, characterizing the p-positions of some and exhibiting equivalences between others.
new results for online page replication. we study the online page replication problem. we present a new randomized online algorithm for rings which is 2.37297-competitive, improving the best previous result of 3.16396. we also show that no randomized online algorithm is better than 1.75037-competitive on the ring; previously, only a 1.58198 bound for a single edge was known. we extend the problem in several new directions: continuous metrics, variable size requests, and replication before service. this yields simplified proofs of several known results.
on the robustness of interconnections in random graphs: a symbolic approach. graphs are models of communication networks. this paper applies symbolic combinatorial techniques in order to characterize the interplay between two parameters of a random graph, namely its density (the number of edges in the graph) and its robustness to link failures. here, robustness means multiple connectivity by short disjoint paths: a triple (g,s,t), where g is a graph and s, t are designated vertices, is called l-robust if s and t are connected via at least two edge-disjoint paths of length at most l. we determine the expected number of ways to get from s to t via two edge-disjoint paths of length l in the classical random graph model gn.p by means of "symbolic" combinatorial methods. we then derive bounds on related threshold probabilities as functions of l and n.
the scientific works of rainer kemp (1949-2004). this short note presents a summary of the scientific contributions of rainer kemp (1949-2004) in the area of discrete mathematics, combinatorial enumeration, and analysis of algorithms. a complete bibliography of kemp's publications is included.
the exact number of squares in fibonacci words. all our words (sequences) are binary. a square is a subword of the form uu (concatenation). two squares are distinct if they are of different shape, not just translates of each other. otherwise they are repeated. fibonacci words are defined by f>sub<0>/sub< = 0, f>sub<1>/sub< = 1, f>sub<m>/sub< = f>sub<m-1>/sub<f>sub<m-2>/sub< for m ? 2. let f>sub<m>/sub< = |f>sub<m>/sub<|. then f>sub<0>/sub< = 1, f>sub<1>/sub< = 1, f>sub<m>/sub< = f>sub<m-1>/sub<+f>sub<m-2>/sub< (m ? 2) are the fibonacci numbers. let d(n) and r(n) be the exact number of distinct and repeated squares respectively in f>sub<n>/sub<. we prove: d(n) = 2(f>sub<n-2>/sub<-1) (n ? 5), which implies, asymptotically, d(n) = 2(2-j)f>sub<n>/sub<+o(1)&#x00a0;&#x00a0;&#x00a0; (2(2-j) < 0.7639), where j is the golden section. we also prove: r(n) = 4/>sub<5>/sub< nf>sub<n>/sub<-2/>sub<5>/sub< (n+6)f>sub<n-1>/sub<-f>sub<n-2>/sub<+n+1 (n ? 3). this yields r(n) = 2/>sub<5>/sub< (3-j)nf>sub<n>/sub<+o(f>sub<n>/sub<) = [(2(3-j))/( 5log>sub<2>/sub< j)]f>sub<n>/sub<log>sub<2>/sub< f>sub<n>/sub<+o(f>sub<n>/sub<) &#x00a0;&#x00a0;&#x00a0; ([(2(3-j))/( 5log>sub<2>/sub< j)] < 0.7962).
d2b: a de bruijn based content-addressable network. we show that the de bruijn graph is appropriate for maintaining dynamic connections, e.g., between the members of a p2p application who join and leave the system at their convenience. we describe the content-addressable network d2b, based on an overlay network preserving de bruijn connections dynamically, and on a distributed hash table (dht) supporting efficient publish and search procedures. the overlay network has constant expected degree, and any publish or search operation in the dht takes a logarithmic expected number of steps.
graph exploration by a finite automaton. a finite automaton, simply referred to as a robot, has to explore a graph whose nodes are unlabeled and whose edge ports are locally labeled at each node. the robot has no a priori knowledge of the topology of the graph or of its size. its task is to traverse all the edges of the graph. we first show that, for any k-state robot and any d ≥ 3, there exists a planar graph of maximum degree d with at most k + 1 nodes that the robot cannot explore. this bound improves all previous bounds in the literature. more interestingly, we show that, in order to explore all graphs of diameter d and maximum degree d, a robot needs ω(d log d) memory bits, even if we restrict the exploration to planar graphs. this latter bound is tight. indeed, a simple dfs up to depth d + 1 enables a robot to explore any graph of diameter d and maximum degree d using a memory of size o(d log d) bits. we thus prove that the worst case space complexity of graph exploration is θ(d log d) bits.
rush hour is pspace-complete, or "why you should generously tip parking lot attendants". rush hour is a children's game that consists of a grid board, several cars that are restricted to move either vertically or horizontally (but not both), a special target car, and a single exit on the perimeter of the grid. the goal of the game is to find a sequence of legal moves that allows the target car to exit the grid. we consider a slightly generalized version of the game that uses an nn grid and assume that we can place the single exit and target car at any location we choose on initialization of the game. in this work, we show that deciding if the target car can legally exit the grid is pspace-complete. our constructive proof uses a lazy form of dual-rail reversible logic such that movement of "output" cars can only occur if logical combinations of "input" cars can also move. emulating this logic only requires three types of devices (two switches and one crossover); thus, our proof technique can be easily generalized to other games and planning problems in which the same three primitive devices can be constructed.
an algebraic characterization of deterministic regular languages over infinite alphabets. we state and prove an infinite alphabet counterpart of the classical myhill-nerode theorem.
on routing of wavebands for all-to-all communications in all-optical paths and cycles. we discuss a model of the all-optical communication technology and an implementation of a simple task, all-to-all, in simple topologies like paths and cycles. the model assumes a single interval (variant of band-pass) filter extracting signal wavelengths for processing and forwarding in intermediate communication nodes. in an attempt to use a minimum number of wavelengths, we give lower and upper bounds on the cardinality of the spectrum used in four cases arising from different assumptions on the topology and the filters. in particular, we propose efficient schedules of directed paths between all pairs of nodes in graphs of maximum node degree two, under the assumption of either a "linear" or "wrapped-around" wavelength spectrum.
semi-dynamic breadth-first search in digraphs. when creating a family of systems, i.e. several systems of similar type which differ within some aspects, it is desirable to be able to express these differences already at the level of the specification, and to automatically obtain systems from it which are ready to run. the use of generic methods may lead to substantial progress in this area. this report explores two aspects: parameterization concepts at the specification level, which can be used to describe variants of a system, and generator programs, which produce runnable systems from prefabricated components.