waashk/dblp huggingface dataset:
the price of anarchy for polynomial social cost. in this work, we consider an interesting variant of the well studied kp model for selfish routing on parallel links, which reflects some influence from the much older wardrop model [j.g. wardrop, some theoretical aspects of road traffic research, proc. inst. of civil eng. part ii 1 (1956) 325-378]. in the new model, user traffics are still unsplittable and links are identical. social cost is now the expectation of the sum, over all links, of latency costs; each latency cost is modeled as a certain polynomial latency cost function evaluated at the latency incurred by all users choosing the link. the resulting social cost is called polynomial social cost, or monomial social cost when the latency cost function is a monomial. all considered polynomials are of degree d, where d ≥ 2, and have non-negative coefficients. we are interested in evaluating nash equilibria in this model, and we use the monomial price of anarchy (mpoa) and the polynomial price of anarchy (ppoa) as our evaluation measures. through establishing some remarkable relations of these costs and measures to some classical combinatorial numbers such as the stirling numbers of the second kind and the bell numbers, we obtain a multitude of results: • for the special case of identical users: the fully mixed nash equilibrium, where all probabilities are strictly positive, maximizes polynomial social cost. the mpoa is no more than bd, the bell number of order d. this immediately implies that the ppoa is no more than σ1 ≤ t ≤ dbt. for the special case of two links, the mpoa is no more than 2d-2(1 + (1/n)d-1), and this bound is tight for n = 2. • the mpoa is exactly ((2d - 1)d/(d - 1)(2d - 2)d-1)((d - 1)/d)d for pure nash equilibria. this immediately implies that the ppoa is no more than σ2 ≤ t ≤ d ((2t - 1)t/(t - 1)(2t - 2)t-1)((t - 1)/t)t.
the complexity of membership problems for circuits over sets of integers. we investigate the complexity of membership problems for {∪, ∩, -, +, ×}-circuits computing sets of integers. these problems are a natural modification of the membership problems for circuits computing sets of natural numbers studied by mckenzie and wagner [the complexity of membership problems for circuits over sets of natural numbers, lecture notes in computer science, vol. 2607, 2003, pp. 571-582]. we show that there are several membership problems for which the complexity in the case of integers differs significantly from the case of the natural numbers: testing membership in the subset of integers produced at the output of a {∪, +, ×}-circuit is nexptime-complete, whereas it is pspace-complete for the natural numbers. as another result, evaluating {-, +}-circuits is shown to be p-complete for the integers and pspace-complete for the natural numbers. the latter result extends mckenzie and wagner's work in nontrivial ways. furthermore, evaluating {×}-circuits is shown to be nl ∧ ⊕l-complete, and several other cases are resolved.
low complexity classes of multidimensional cellular automata. in this paper, multidimensional cellular automaton are considered. we investigate the hierarchy designed by the low complexity classes when the dimensionality is increased. whether this hierarchy is strict, is an open problem. however, we compare different variants and study their closure properties. we present also a correspondence between a main variant of multidimensional real-time cellular automata and one-way multihead alternating finite automata.
label updating to avoid point-shaped obstacles in fixed model. in this paper, we present efficient algorithms for updating the labeling of a set of n points after the presence of a random obstacle that appears on the map repeatedly. we update the labeling so that the given obstacle does not appear in any of the labels, the new labeling is valid, and the labels are as large as possible (called the optimal labeling). each point is assumed to have an axis-parallel, square-shaped label of unit size, attached exclusively to that point in the middle of one of its edges. we consider two models: (1) the 2pm model, where each label is attached to its feature only on the middle of one of its horizontal edges, and (2) the r4pm model, where each label is attached to its feature on the middle of either one of its horizontal or vertical edges (known in advance). we assume that a sequence of point-shaped obstacles appear on the map on random locations. three settings are considered for the behavior of the obstacle: (1) the obstacle is removed afterwards, (2) it remains on the map, and (3) it receives a similar label and remains on the map. only two operations are permitted on the labels: flipping one or more labels, and/or resizing all labels. in the first setting, we suggest a data structure of o(n) space and o(n lg n) time in the 2pm model, and of o(n2) time in the r4pm model, so that the updated labeling can be constructed for any obstacle position in o(lgn + k) time, where k is the minimum number of operations needed. for the second and third problems, we suggest an o(n) space and o(n lg n) time data structure that can place each obstacle (possibly with a label) on the map in o(lgn + k) time, if k label flips are sufficient to make room to place the new obstacle. otherwise, two o(n) time algorithms are suggested when a relabeling of all points is required.
on the remote server problem or more about tcp acknowledgments. we study an on-line problem that is motivated by service calls management in a remote support center. when a customer calls the remote support center of a software company, a technician opens a service request and assigns it a severity rating. this request is then transferred to the appropriate support engineer (se) who establishes a connection to the customer's site and uses remote diagnostic capabilities to resolve the problem. we assume that the se can service at most one customer at time and a request service time is negligible. there is a constant setup cost of creating a new connection to a customer's site and a specific cost per request for delaying its service that depends on the severity of the request. the problem is to decide which customers to serve first so as to minimize the incurred cost. this problem with just two customers is a natural generalization of the tcp acknowledgment problem. for the on-line version of the remote server problem (rsp), we present algorithms for the general case and for a special case of two customers that achieve competitive ratios of exactly 4 and 3, respectively. we also show that no deterministic on-line algorithm can have competitive ratio better than 3. then we study generalized versions of our model, these are the case of an asymmetric setup cost function and the case of multiple ses. for the off-line version of the rsp, we derive an optimal algorithm with a polynomial running time for a constant number of customers.
pairwise edge disjoint shortest paths in the n-cube. complexity issues intrinsic to certain fundamental data dissemination problems in high-performance network topologies are discussed. in particular, we study the p-pairwise edge disjoint shortest paths problem. an efficient algorithm for the case when every source point is at a distance at most two from its target is presented and for pairs at a distance at most three we show that the problem is np-complete.
sharing the cost of multicast transmissions in wireless networks. a crucial issue in non-cooperative wireless networks is that of sharing the cost of multicast transmissions to different users residing at the stations of the network. each station acts as a selfish agent that may misreport its utility (i.e., the maximum cost it is willing to incur to receive the service, in terms of power consumption) in order to maximize its individual welfare, defined as the difference between its true utility and its charged cost. a provider can discourage such deceptions by using a strategyproof cost sharing mechanism, that is a particular public algorithm that, by forcing the agents to truthfully reveal their utility, starting from the reported utilities, decides who gets the service (the receivers) and at what price. a mechanism is said budget balanced (bb) if the receivers pay exactly the (possibly minimum) cost of the transmission, and β-approximate budget balanced (β-bb) if the total cost charged to the receivers covers the overall cost and is at most β times the optimal one, while it is efficient if it maximizes the sum of the receivers' utilities minus the total cost over all receivers' sets. in this paper, we first investigate cost sharing strategyproof mechanisms for symmetric wireless networks, in which the powers necessary for exchanging messages between stations may be arbitrary and we provide mechanisms that are either efficient or bb when the power assignments are induced by a fixed universal spanning tree, or (3 ln(k + 1))-bb (k is the number of receivers), otherwise. then we consider the case in which the stations lay in a d-dimensional euclidean space and the powers fall as 1/dα, and provide strategyproof mechanisms that are either 1-bb or efficient for α = 1 or d = 1. finally, we show the existence of 2(3d - 1)-bb strategyproof mechanisms in any d-dimensional space for every α ≥ d. for the special case of d = 2 such a result can be improved to achieve 12-bb mechanisms.
algebraic properties of substitution on trajectories. language operations on trajectories provide a generalization of many common operations such as concatenation, quotient, shuffle and others. a trajectory is a syntactical condition determining positions where an operation is applied. besides their elegant language-theoretical properties, the operations on trajectories have been used to solve problems in coding theory, bioinformatics and concurrency theory. we focus on algebraic properties of substitution on trajectories. their characterization in terms of language-theoretical properties of the associated sets of trajectories is given. the transitivity property is of particular interest. unlike, e.g., shuffle on trajectories, in the case of substitution the transitive closure of a regular set of trajectories is again regular. this result has consequences in the above-mentioned application areas.
a geometric characterization of automatic semigroups. in the study of automatic groups, the geometrical characterization of automaticity (in terms of the "fellow traveller property") plays a fundamental role. when we move to the study of automatic semigroups, we no longer have this simple formulation. the purpose of this paper is to give a general geometric characterization of automaticity in semigroups.
partial multicuts in trees. let t = (v, e) be an undirected tree, in which each edge is associated with a non-negative cost, and let {s1, t1},..., {sk, tk} be a collection of k distinct pairs of vertices. given a requirement parameter t ≤ k, the partial multicut on a tree problem asks to find a minimum cost set of edges whose removal from t disconnects at least t out of these k pairs. this problem generalizes the well-known multicut on a tree problem, in which we are required to disconnect all given pairs. the main contribution of this paper is an (8/3 + ε)-approximation algorithm for partial multicut on a tree, whose run time is strongly polynomial for any fixed ε > 0. this result is achieved by introducing problem-specific insight to the general framework of using the lagrangian relaxation technique in approximation algorithms. our algorithm utilizes a heuristic for the closely related prize-collecting variant, in which we are not required to disconnect all pairs, but rather incur penalties for failing to do so. we provide a lagrangian multiplier preserving algorithm for the latter problem, with an approximation factor of 2. finally, we present a new 2-approximation algorithm for multicut on a tree, based on lp-rounding.
enumeration of subtrees of trees. let t be a weighted tree. the weight of a subtree t1 of t is defined as the product of weights of vertices and edges of t1. we obtain a linear-time algorithm to count the sum of weights of subtrees of t. as applications, we characterize the tree with the diameter at least d, which has the maximum number of subtrees, and we characterize the tree with the maximum degree at least δ, which has the minimum number of subtrees.
one head machines from a symbolic approach. we consider the turing machine as a dynamical system and we study a particular partition projection of it. in this way, we define a language (a subshift) associated to each machine. the classical definition of turing machines over a one-dimensional tape is generalized to allow for a tape in the form of a cayley graph. we study the complexity of the language of a machine in terms of realtime recognition by putting it in relation with the structure of its tape. in this way, we find a large set of realtime subshifts some of which are proved not to be deterministic in realtime. sofic subshifts of this class correspond to machines that cannot make arbitrarily large tours. we prove that these machines always have an ultimately periodic behavior when starting with a periodic initial configuration, and this result is proved for any cayley graph.
binary matrices under the microscope: a tomographical problem. a binary matrix can be scanned by moving a fixed rectangular window (sub-matrix) across it, rather like examining it closely under a microscope. with each viewing, a convenient measurement is the number of 1s visible in the window, which might be thought of as the luminosity of the window. the rectangular scan of the binary matrix is then the collection of these luminosities presented in matrix form. we show that, at least in the technical case of a smoothmxn binary matrix, it can be reconstructed from its rectangular scan in polynomial time in the parameters m and n, where the degree of the polynomial depends on the size of the window of inspection. for an arbitrary binary matrix, we then extend this result by determining the entries in its rectangular scan that preclude the smoothness of the matrix.
an efficient alignment algorithm for masked sequences. we consider the alignment problem where sequences may have masked regions. the bases in masked regions are either unspecified or unknown, and they will be denoted by n. we present an efficient algorithm that finds an optimal local alignment by skipping such masked regions of sequences. our algorithm works for both the affine gap penalty model and the linear gap penalty model. the time complexity of our algorithm is o((n-t)(m-s)+vm+wn) time, where n and m are the lengths of given sequences a and b, t and s are the numbers of base n in a and b, and v and w are the numbers of masked regions in a and b, respectively.
on searching a table consistent with division poset. suppose p"n={1,2,...,n} is a partially ordered set with the partial order defined by divisibility, that is, for any two elements i,j@?p"n satisfying i divides j, we have i@?"p"""nj. a table a"n={a"i|i=1,2,...,n} of real numbers is said to be consistent with p"n, provided that for any two elements i,j@?{1,2,...,n} satisfying i divides j, a"i@?a"j. given a real number x, we want to determine whether x@?a"n, by comparing x with as few entries of a"n as possible. in this paper, we investigate the complexity @t(n), measured by the number of comparisons, of the above search problem. we present a 55n72+o(ln^2n) search algorithm for a"n and prove a lower bound (34+172160)n+o(1) on @t(n) using an adversary argument.
solving shortest paths efficiently on nearly acyclic directed graphs. shortest path problems can be solved very efficiently when a directed graph is nearly acyclic. earlier results defined a graph decomposition, now called the 1-dominator set, which consists of a unique collection of acyclic structures with each single acyclic structure dominated by a single associated trigger vertex. in this framework, a specialised shortest path algorithm only spends delete-min operations on trigger vertices, thereby making the computation of shortest paths through non-trigger vertices easier. a previously presented algorithm computed the 1-dominator set in o(mn) worst-case time, which allowed it to be integrated as part of an o(mn+nrlogr) time all-pairs algorithm. here m and n respectively denote the number of edges and vertices in the graph, while r denotes the number of trigger vertices. a new algorithm presented in this paper computes the 1-dominator set in just o(m) time. this can be integrated as part of the o(m+rlogr) time spent solving single-source, improving on the value of r obtained by the earlier tree-decomposition single-source algorithm. in addition, a new bidirectional form of 1-dominator set is presented, which further improves the value of r by defining acyclic structures in both directions over edges in the graph. the bidirectional 1-dominator set can similarly be computed in o(m) time and included as part of the o(m+rlogr) time spent computing single-source. this paper also presents a new all-pairs algorithm under the more general framework where r is defined as the size of any predetermined feedback vertex set of the graph, improving the previous all-pairs time complexity from o(mn+nr^2) to o(mn+r^3).
on the relationship between atsp and the cycle cover problem. in this paper, we study the relationship between the asymmetric traveling salesman problem (atsp) and the cycle cover problem in terms of the strength of the triangle inequality on the edge costs in the given complete directed graph instance, g=(v,e). the strength of the triangle inequality is captured by parametrizing the triangle inequality as follows. a complete directed graph g=(v,e) with a cost function c:e->r^+ is said to satisfy the @c-parametrized triangle inequality if @c(c(u,w)+c(w,v))>=c(u,v) for all distinct u,v,w@?v. then the graph g is called a @c-triangular graph. for any @c-triangular graph g, for @c=1, the ratio atsp(g)ap(g) can become unbounded. the upper bound is shown constructively and can also be viewed as an approximation algorithm for atsp with parametrized triangle inequality. we also consider the following problem: in a @c-triangular graph, does there exist a function f(@c) such that c"m"a"xc"m"i"n is bounded above by f(@c)? (here c"m"a"x and c"m"i"n are the costs of the maximum cost and minimum cost edges respectively.) we show that when @c=13, no such function f(@c) exists.
induced-path partition on graphs with special blocks. in a graph, an induced path is a path v"0,v"1,...,v"r in which a vertex v"i is adjacent to another vertex v"j if and only if |i-j|=1. an induced-path partition of a graph is a collection of vertex-disjoint induced paths that cover all vertices of the graph. the induced-path-partition problem is to determine the minimum cardinality of an induced-path partition of a graph. this paper presents an o(|v|+|e|)-time algorithm for the induced-path-partition problem on graphs whose blocks are complete graphs, cycles or complete bipartite graphs.
obtaining shorter regular expressions from finite-state automata. we consider the use of state elimination to construct shorter regular expressions from finite-state automata (fas). although state elimination is an intuitive method for computing regular expressions from fas, the resulting regular expressions are often very long and complicated. we examine the minimization of fas to obtain shorter expressions first. then, we introduce vertical chopping based on bridge states and horizontal chopping based on the structural properties of given fas. we prove that we should not eliminate bridge states until we eliminate all non-bridge states to obtain shorter regular expressions. in addition, we suggest heuristics for state elimination that leads to shorter regular expressions based on vertical chopping and horizontal chopping.
feasibility and complexity of broadcasting with random transmission failures. fault-tolerant broadcasting in the message passing and radio models is considered under a probabilistic failure model. at each step, the transmitter of each node may fail with fixed constant probability p
quantifier elimination for the reals with a predicate for the powers of two. in 1985, van den dries showed that the theory of the reals with a predicate for the integer powers of two admits quantifier elimination in an expanded language, and is hence decidable. he gave a model-theoretical argument, which provides no apparent bounds on the complexity of a decision procedure. we provide a syntactical argument that yields a procedure that is primitive recursive, although not elementary. in particular, we show that it is possible to eliminate a single block of existential quantifiers in time 2"o"("n")^0, where n is the length of the input formula and 2"k^x denotes k-fold iterated exponentiation.
the left-right-imbalance of binary search trees. we present a detailed study of left-right-imbalance measures for random binary search trees under the random permutation model, i.e., where binary search trees are generated by random permutations of {1,2,...,n}. for random binary search trees of size n we study (i) the difference between the left and the right depth of a randomly chosen node, (ii) the difference between the left and the right depth of a specified node j=j(n), and (iii) the difference between the left and the right pathlength, and show for all three imbalance measures limiting distribution results.
a note on efficient aggregate queries in sensor networks. we consider a scenario where nodes in a sensor network hold numeric items, and the task is to evaluate simple functions of the distributed data. in this note we present distributed protocols for computing the median with sublinear space and communication complexity per node. specifically, we give a deterministic protocol for computing median with polylog complexity and a randomized protocol that computes an approximate median with polyloglog communication complexity per node. on the negative side, we observe that any deterministic protocol that counts the number of distinct data items must have linear complexity in the worst case.
longest common subsequence problem for unoriented and cyclic strings. given a finite set of strings x, the longest common subsequence problem (lcs) consists in finding a subsequence common to all strings in x that is of maximal length. lcs is a central problem in stringology and finds broad applications in text compression, conception of error-detecting codes, or biological sequence comparison. however, in numerous contexts, words represent cyclic or unoriented sequences of symbols and lcs must be generalized to consider both orientations and/or all cyclic shifts of the strings involved. this occurs especially in computational biology when genetic material is sequenced from circular dna or rna molecules. in this work, we define three variants of lcs when the input words are unoriented and/or cyclic. we show that these problems are np-hard, and w[1]-hard if parameterized in the number of input strings. these results still hold even if the three lcs variants are restricted to input languages over a binary alphabet. we also settle the parameterized complexity of our problems for most relevant parameters. moreover, we study the approximability of these problems: we discuss the existence of approximation bounds depending on the cardinality of the alphabet, on the length of the shortest sequence, and on the number of input sequences. for this we prove that maximum independent set in r-uniform hypergraphs is w[1]-hard if parameterized in the cardinality of the sought independent set and at least as hard to approximate as maximum independent set in graphs.