waashk/dblp huggingface dataset:
quantum approaches to graph colouring. in this paper, we investigate quantum algorithms for graph colouring problems, in particular for 2- and 3-colouring of graphs. our main goal is to establish a set of quantum representations and operations suitable for the problem at hand. we propose unitary- as well as measurement-based quantum computations, also taking inspiration from answer set programming, a form of declarative programming close to traditional logic programming. the approach used is one in which we first generate arbitrary solutions to the problem, then constraining these according to the problem's input. though we do not achieve fundamental speed-ups, our algorithms show how quantum concepts can be used for programming and moreover exhibit structural differences. for example, we compute all possible colourings at the same time. we compare our algorithms with classical ones, highlighting how the same type of difficulties give rise to np-complete behaviour, and propose possible improvements.
a more effective linear kernelization for cluster editing. in the np-hard cluster editing problem, we have as input an undirected graph g and an integer k>=0. the question is whether we can transform g, by inserting and deleting at most k edges, into a cluster graph, that is, a union of disjoint cliques. we first confirm a conjecture by michael fellows [iwpec 2006] that there is a polynomial-time kernelization for cluster editing that leads to a problem kernel with at most 6k vertices. more precisely, we present a cubic-time algorithm that, given a graph g and an integer k>=0, finds a graph g^' and an integer k^'@?k such that g can be transformed into a cluster graph by at most k edge modifications iff g^' can be transformed into a cluster graph by at most k^' edge modifications, and the problem kernel g^' has at most 6k vertices. so far, only a problem kernel of 24k vertices was known. second, we show that this bound for the number of vertices of g^' can be further improved to 4k vertices. finally, we consider the variant of cluster editing where the number of cliques that the cluster graph can contain is stipulated to be a constant d>0. we present a simple kernelization for this variant leaving a problem kernel of at most (d+2)k+d vertices.
on weighted balls-into-bins games. we consider the well-known problem of randomly allocating m balls into n bins. we investigate various properties of single-choice games as well as multiple-choice games in the context of weighted balls. we are particularly interested in questions that are concerned with the distribution of ball weights, and the order in which balls are allocated. do any of these parameters influence the maximum expected load of any bin, and if yes, then how? the problem of weighted balls is of practical relevance. balls-into-bins games are frequently used to conveniently model load balancing problems. here, weights can be used to model resource requirements of the jobs, i.e., memory or running time.
the subdivision-constrained minimum spanning tree problem. motivated by the constrained minimum spanning tree (cst) problem in hassin and levin [r. hassin, a. levin, an efficient polynomial time approximation scheme for the constrained minimum spanning tree problem using matroid intersection, siam journal on computing 33 (2) (2004) 261-268], we study a new combinatorial optimization problem in this paper, called the general subdivision-constrained spanning tree problem (gscst): given a graph g=(v,e;w,c) with two nonnegative integers w(e) and c(e) for each edge e&isin;e, two positive integers b and d, the gscst problem is to first find a spanning tree t=(v,et) of g with weight &sigma;e&isin;etw(e)&le;b and then to insert some new vertices on some suitable edges in t such that each edge in the subdivision tree t' of t has its weight not beyond d. the objective is to minimize the cost &sigma;e&isin;etinsert(e)c(e) of such new vertices inserted on the suitable edges among all spanning trees of g subject to the two preceding constraints, where a subdivision tree t' of t is constructed by inserting some new vertices on the suitable edges in t, the value insert(e)=[w(e)/d] - 1 is the least number of vertices inserted and c(e) is the cost of each vertex inserted on the edge e. we obtain the following main results: (1) the gscst problem and its variant are still np-hard, by a reduction from the 0-1 knapsack problem, respectively; (2) the gscst problem as well as its variant is polynomially equivalent to the cst problem, which implies the existence of a polynomial time approximation scheme to solve the gscst problem and its variant; (3) we finally design three strongly polynomial time algorithms to solve the special versions of the gscst problem and its variant, respectively.
efficient algorithms to compute compressed longest common substrings and compressed palindromes. this paper studies two problems on compressed strings described in terms of straight line programs (slps). one is to compute the length of the longest common substring of two given slp-compressed strings, and the other is to compute all palindromes of a given slp-compressed string. in order to solve these problems efficiently (in polynomial time w.r.t. the compressed size) decompression is never feasible, since the decompressed size can be exponentially large. we develop combinatorial algorithms that solve these problems in o(n4logn) time with o(n3) space, and in o(n4) time with o(n2) space, respectively, where n is the size of the input slp-compressed strings.
towards a real-time distributed computing model. this paper introduces a simple real-time distributed computing model for message-passing systems, which reconciles the distributed computing and the real-time systems perspective: by just replacing instantaneous computing steps with computing steps of non-zero duration, we obtain a model that both facilitates real-time scheduling analysis, and retains compatibility with classic distributed computing analysis techniques and results. we provide general simulations and validity conditions for transforming algorithms from the classic synchronous model to our real-time model and vice versa, and investigate whether/which properties of real systems are inaccurately or even wrongly captured when resorting to zero step-time models. we revisit the well-studied problem of deterministic drift- and failure-free internal clock synchronization for this purpose, and show that no clock synchronization algorithm with constant running time can achieve optimal precision in our real-time model. since such an algorithm is known for the classic model, this is an instance of a problem where the standard distributed computing analysis gives too optimistic results. we prove that optimal precision is only achievable with algorithms that take @w(n) time in our model, and establish several additional algorithms and lower bounds.
approximation algorithm for maximum edge coloring. we propose a polynomial time approximation algorithm for a novel maximum edge coloring problem which arises from wireless mesh networks [ashish raniwala, tzi-cker chiueh, architecture and algorithms for an ieee 802.11-based multi-channel wireless mesh network, in: infocom 2005, pp. 2223-2234; ashish raniwala, kartik gopalan, tzi-cker chiueh, centralized channel assignment and routing algorithms for multi-channel wireless mesh networks, mobile comput. commun. rev. 8 (2) (2004) 50-65]. the problem is to color all the edges in a graph with maximum number of colors under the following q-constraint: for every vertex in the graph, all the edges incident to it are colored with no more than q (q@?z,q>=2) colors. we show that the algorithm is a 2-approximation for the case q=2 and a (1+4q-23q^2-5q+2)-approximation for the case q>2 respectively. the case q=2 is of great importance in practice. for complete graphs and trees, polynomial time accurate algorithms are found for them when q=2. the approximation algorithm gives a feasible solution to channel assignment in multi-channel wireless mesh networks.
the price of optimum in stackelberg games on arbitrary single commodity networks and latency functions. let m be a single s-t network of parallel links with load dependent latency functions shared by an infinite number of selfish users. this may yield a nash equilibrium with unbounded coordination ratio [e. koutsoupias, c. papadimitriou, worst-case equilibria, in: 16th annual symposium on theoretical aspects of computer science, stacs, vol. 1563, 1999, pp. 404-413; t. roughgarden, e. tardos, how bad is selfish routing? in: 41st ieee annual symposium of foundations of computer science, focs, 2000, pp. 93-102]. a leader can decrease the coordination ratio by assigning flow &alpha;r on m, and then all followers assign selfishly the (1-&alpha;)r remaining flow. this is a stackelberg scheduling instance(m,r,&alpha;),0&le;&alpha;&le;1. it was shown [t. roughgarden, stackelberg scheduling strategies, in: 33rd annual symposium on theory of computing, stoc, 2001, pp. 104-113] that it is weakly np-hard to compute the optimal leader's strategy. for any such network m we efficiently compute the minimum portion @b"m of flow r>0 needed by a leader to induce m's optimum cost, as well as her optimal strategy. this shows that the optimal leader's strategy on instances (m,r,@a>=@b"m) is in p. unfortunately, stackelberg routing in more general nets can be arbitrarily hard. roughgarden presented a modification of braess's paradox graph, such that no strategy controlling &alpha;r flow can induce &le;1/&alpha; times the optimum cost. however, we show that our main result also applies to any s-t net g. we take care of the braess's graph explicitly, as a convincing example. finally, we extend this result to k commodities. a conference version of this paper has appeared in [a. kaporis, p. spirakis, the price of optimum in stackelberg games on arbitrary single commodity networks and latency functions, in: 18th annual acm symposium on parallelism in algorithms and architectures, spaa, 2006, pp. 19-28]. some preliminary results have also appeared as technical report in [a.c. kaporis, e. politopoulou, p.g. spirakis, the price of optimum in stackelberg games, in: electronic colloquium on computational complexity, eccc, (056), 2005].
adversarial queuing theory with setups. we look at routing and scheduling problems on kelly type networks where the injection process is under the control of an adversary. the novelty of the model we consider is that the adversary injects requests of distinct types. resources are subject to switch-over delays or setups when they begin servicing a new request class. in this new setting, we study the behavior of sensible policies as introduced by dai and jennings [j. dai, o. jennings, stabilizing queueing networks with setups, math. oper. res. (2004) 891-922]. we first show that the model is robust in the sense that under some mild conditions universal stability of work conserving packet routing protocols is preserved for natural variants of the underlying model. also, the model's equivalence to so called token networks is established. we adapt to the multi-type request and setup setting, standard arguments for proving stability. nevertheless, we provide counterexamples that show that for several reasonable adaptations of contention resolution protocols to the multi-type case, stability results do not carry over from the single-type scenario. this motivates us to explore fluid model based arguments that could be used for proving stability for a given network. specifically we show analogues of results obtained by gamarnik [d. gamarnik, stability of adversarial queues via fluid model, in: proc. of the 39th annual symposium on foundations of computer science, 1998, pp. 60-70] but in the multi-type request with setups scenario.
safe termination detection in an asynchronous distributed system when processes may crash and recover. the termination detection problem involves detecting whether an ongoing distributed computation has ceased all its activities. we investigate the termination detection problem in an asynchronous distributed system under the crash-recovery model. it has been shown that the problem is impossible to solve under the crash-recovery model in general. we identify two conditions under which the termination detection problem can be solved in a safe manner. we also propose algorithms to detect termination under the conditions identified.
glance: a lightweight querying service for wireless sensor networks. distance-sensitivity guarantee in querying is a highly desirable property in wireless sensor networks as it limits the cost of executing a ''query'' operation to be within a constant factor of the distance to the nearest node that contains an answer. however, such a tight guarantee may require building an infrastructure for efficient resolution of queries, and the cost of maintaining this infrastructure may be prohibitive. here we show that it is possible to implement distance-sensitive querying in an efficient way by exploiting the geometry of the network. our querying service glance ensures that a ''query'' operation invoked within d distance of an event intercepts the event's ''advertise'' operation within d*s distance, where s is a ''stretch-factor'' tunable by the user.
a quadratic time 2-approximation algorithm for block sorting. the block sorting problem is the problem of minimizing the number of steps to sort a list of distinct items, where a sublist of items which are already in sorted order, called a block, can be moved in one step. we give an approximation algorithm for the block sorting problem with an approximation ratio of 2 and run time o(n^2). the approximation algorithm is based on the related concept of block deletion. we show that finding an optimum block deletion sequence can be done in o(n^2) time, even though block sorting is known to be np-hard. block sorting has importance in connection with optical character recognition (ocr) and is related to transposition sorting in computational biology.
meadows and the equational specification of division. the rational, real and complex numbers with their standard operations, including division, are partial algebras specified by the axiomatic concept of a field. since the class of fields cannot be defined by equations, the theory of equational specifications of data types cannot use field theory in applications to number systems based upon rational, real and complex numbers. we study a new axiomatic concept for number systems with division that uses only equations: a meadow is a commutative ring with a total inverse operator satisfying two equations which imply 0^-^1=0. all fields and products of fields can be viewed as meadows. after reviewing alternate axioms for inverse, we start the development of a theory of meadows. we give a general representation theorem for meadows and find, as a corollary, that the conditional equational theory of meadows coincides with the conditional equational theory of zero totalized fields. we also prove representation results for meadows of finite characteristic.
on the support size of stable strategies in random games. in this paper we study the support sizes of evolutionary stable strategies (ess) in random evolutionary games. we prove that, when the elements of the payoff matrix behave either as uniform, or normally distributed random variables, almost all ess have support sizes o(n), where n is the number of possible types for a player. our arguments are based exclusively on a stability property that the payoff submatrix indicated by the support of an ess must satisfy. we then combine this result with a recent result of mclennan and berg [a. mclennan, j. berg, the asymptotic expected number of nash equilibria of two player normal form games, games and economic behavior 51 (2005) 264-295], concerning the expected number of nash equilibria in normal-random bimatrix games, to show that the expected number of ess is significantly smaller than the expected number of symmetric nash equilibria of the underlying symmetric bimatrix game.
fast payment schemes for truthful mechanisms with verification. in this paper we study optimization problems with verifiable one-parameter selfish agents introduced by auletta et al. [v. auletta, r. de prisco, p. penna, p. persiano, the power of verification for one-parameter agents, in: proceedings of the 31st international colloquium on automata, languages and programming, icalp, in: lncs, vol. 3142, 2004, pp. 171-182]. our goal is to allocate load among the agents, provided that the secret data of each agent is a single positive real number: the cost they incur per unit load. in such a setting the payment is given after the load completion, therefore if a positive load is assigned to an agent, we are able to verify if the agent declared to be faster than she actually is. we design truthful mechanisms when the agents' type sets are upper-bounded by a finite value. we provide a truthful mechanism that is c&middot;(1+&epsilon;)-approximate if the underlying algorithm is c-approximate and weakly-monotone. moreover, if type sets are also discrete, we provide a truthful mechanism preserving the approximation ratio of its algorithmic part. our results improve the existing ones which provide truthful mechanisms dealing only with finite type sets and do not preserve the approximation ratio of the underlying algorithm. finally, we give applications for our payment schemes. firstly, we give a full characterization of the q‖cmax problem by using our techniques. even if our payment schemes need upper-bounded type sets, every instance of q‖cmax can be "mapped" into an instance with upper-bounded type sets preserving the approximation ratio. in conclusion, we turn our attention to binary demand games. in particular, we show that the minimum radius spanning tree admits an exact truthful mechanism with verification achieving time (and space) complexity of the fastest centralized algorithm for it. this contrasts with a recent truthful mechanism for the same problem [g. proietti, p. widmayer, a truthful mechanism for the non-utilitarian minimum radius spanning tree problem, in: proceedings of the 17th acm symposium on parallelism in algorithms and architectures, spaa, acm press, 2005, pp. 195-202] which pays a linear factor with respect to the complexity of the fastest centralized algorithm. such a result is extended to several binary demand games studied in literature.
robust self-stabilizing weight-based clustering algorithm. ad hoc networks consist of wireless hosts that communicate with each other in the absence of a fixed infrastructure. such networks cannot rely on centralized and organized network management. the clustering problem consists of partitioning network nodes into non-overlapping groups called clusters. clusters give a hierarchical organization to the network that facilitates network management and that increases its scalability. in a weight-based clustering algorithm, the clusterheads are selected according to their weight (a node's parameter). the higher the weight of a node, the more suitable this node is for the role of clusterhead. in ad hoc networks, the amount of bandwidth, memory space or battery power of a node could be used to determine weight values. a self-stabilizing algorithm, regardless of the initial system configuration, converges to legitimate configurations without external intervention. due to this property, self-stabilizing algorithms tolerate transient faults and they are adaptive to any topology change. in this paper, we present a robust self-stabilizing weight-based clustering algorithm for ad hoc networks. the robustness property guarantees that, starting from an arbitrary configuration, after one asynchronous round, the network is partitioned into clusters. after that, the network stays partitioned during the convergence phase toward a legitimate configuration where the clusters verify the ''ad hoc clustering properties''.
on small, reduced, and fast universal accepting networks of splicing processors. in this paper, we show that accepting networks of splicing processors (ansps) of size 2 are computationally complete. since, by definition, an ansp needs at least two nodes to perform non-trivial computations, this completely settles the question of designing complete ansps of minimal size. also, we derive from this result the fact that all the languages in pspace can be accepted by ansps of size 2, having polynomial length complexity (the ansp complexity measure for the space used in a computation). however, the construction that we propose, although efficient from the descriptional complexity and space complexity points of view, does not seem to have good properties from the time complexity point of view. in this respect, we prove that ansps of size three can decide all languages in np in polynomial time. the previous lower bound on size for both completeness and efficient acceptance of np-languages was seven. we also consider ansps with restricted features, proving the following normal forms: for any ansp there exists an equivalent ansp without input filters, and one without output filters. finally, we show how to construct a small universal ansp and make several considerations on the computational efficiency of universal ansps.
a note on universal composable zero-knowledge in the common reference string model. pass observed that universal composable zero-knowledge (uczk) protocols in the common reference string (crs) model lose deniability that is a natural security property and implication of the zk functionality in accordance with the uc framework. an open problem (or, natural query) raised in the literature is: are there any other essential security properties, other than the well-known deniability property, that could be lost by uczk in the crs model, in comparison with the zk functionality in accordance with the uc framework? in this work, we answer this open question (or, natural query), by showing that when running concurrently with other protocols uczk in the crs model can lose proof of knowledge (pok) property that is very essential and core security implication of the zk functionality. this is demonstrated by concrete attack against naturally existing uczk protocols in the crs model. then, motivated by our attack, we make further clarifications of the underlying reasons beneath the concrete attack, and investigate the precise security guarantee of uc with crs.
the complexity of the matroid-greedoid partition problem. we show that the maximum matroid-greedoid partition problem is np-hard to approximate to within 1/2+&epsilon; for any &epsilon;>0, which matches the trivial factor 1/2 approximation algorithm. the main tool in our hardness of approximation result is an extractor code with polynomial rate, alphabet size and list size, together with an efficient algorithm for list-decoding. we show that the recent extractor construction of guruswami, umans and vadhan [v. guruswami, c. umans, s.p. vadhan, unbalanced expanders and randomness extractors from parvaresh-vardy codes, in: ieee conference on computational complexity, ieee computer society, 2007, pp. 96-108] can be used to obtain a code with these properties. we also show that the parameterized matroid-greedoid partition problem is fixed-parameter tractable.