waashk/dblp huggingface dataset:
strongly polynomial-time truthful mechanisms in one shot. one of the main challenges in algorithmic mechanism design is to turn (existing) efficient algorithmic solutions into efficient truthful mechanisms. building a truthful mechanism is indeed a difficult process since the underlying algorithm must obey certain ''monotonicity'' properties and suitable payment functions need to be computed (this task usually represents the bottleneck in the overall time complexity). we provide a general technique for building truthful mechanisms that provide optimal solutions in strongly polynomial time. we show that the entire mechanism can be obtained if one is able to express/write a strongly polynomial-time algorithm (for the corresponding optimization problem) as a ''suitable combination'' of simpler algorithms. this approach applies to a wide class of mechanism design graph problems, where each selfish agent corresponds to a weighted edge in a graph (the weight of the edge is the cost of using that edge). our technique can be applied to several optimization problems which prior results cannot handle (e.g., min-max optimization problems). as an application, we design the first (strongly polynomial-time) truthful mechanism for the minimum diameter spanning tree problem, by obtaining it directly from an existing algorithm for solving this problem. for this non-utilitarian min-max problem, no truthful mechanism was known, even considering those running in exponential time (indeed, exact algorithms do not necessarily yield truthful mechanisms). also, standard techniques for payment computations may result in a running time which is not polynomial in the size of the input graph. the overall running time of our mechanism, instead, is polynomial in the number n of nodes and m of edges, and it is only a factor o(n@a(n,n)) away from the best known canonical centralized algorithm.
market equilibria with hybrid linear-leontief utilities. we introduce a new family of utility functions for exchange markets. this family provides a natural and ''continuous'' hybridization of the traditional linear and leontief utilities and might be useful in understanding the complexity of computing approximating market equilibria, although computing an equilibrium in a market with this family of utility functions, this is ppad-hard in general. in this paper, we present an algorithm for finding an approximate arrow-debreu equilibrium when the leontief components of the market are grouped, finite and well-conditioned.
on the construction of free algebras for equational systems. the purpose of this paper is threefold: to present a general abstract, yet practical, notion of equational system; to investigate and develop the finitary and transfinite construction of free algebras for equational systems; and to illustrate the use of equational systems as needed in modern applications.
universal augmentation schemes for network navigability. augmented graphs were introduced for the purpose of analyzing the ''six degrees of separation between individuals'' observed experimentally by the sociologist standley milgram in the 60's. we define an augmented graph as a pair (g,m) where g is an n-node graph with nodes labeled in {1,...,n}, and m is an nxn stochastic matrix. every node u@?v(g) is given an extra link, called a long range link, pointing to some node v, called the long range contact of u. the head v of this link is chosen at random by pr{u->v}=m"u","v. in augmented graphs, greedy routing is the oblivious routing process in which every intermediate node chooses from among all its neighbors (including its long range contact) the one that is closest to the target according to the distance measured in the underlying graph g, and forwards to it. the best augmentation scheme known so far ensures that, for any n-node graph g, greedy routing performs in o(n) expected number of steps. our main result is the design of an augmentation scheme that overcomes the o(n) barrier. precisely, we prove that for any n-node graph g whose nodes are arbitrarily labeled in {1,...,n}, there exists a stochastic matrix m such that greedy routing in (g,m) performs in o@?(n^1^/^3), where the o@? notation ignores the polylogarithmic factors. we prove additional results when the stochastic matrix m is universal to all graphs. in particular, we prove that the o(n) barrier can still be overcame for large graph classes even if the matrix m is universal. this however requires an appropriate labeling of the nodes. if the node labeling is arbitrary, then we prove that the o(n) barrier cannot be overcome with universal matrices.
investigating the existence and the regularity of logarithmic harary graphs. this paper studies the existence and the regularity of logarithmic harary graphs (lhgs). this study is motivated by the fact that these graphs are employed for modeling the communication topology to support efficient flooding in the presence of link and node failures when considering an initial arbitrary number of nodes n. therefore, the capability to identify graph constraints that allow the construction of lhgs for the largest number of pairs (n,k) (where k is the desired degree of connectivity to be tolerant to failures) becomes of primary importance. the paper presents several results in that direction. we introduce a graph constraint, namely k-pasted-tree, that allows the construction of a lhg for every pair (n,k) such that n>=2k. secondly we present another graph constraint for lhg, namely k-diamond, which is equivalent to k-pasted-tree in terms of capability to construct lhgs for any pair (n,k). the interest of k-diamond lies in the fact that, for a given k, k-diamond allows us to construct more regular graphs than k-pasted-tree does. a k-regular graph shows the minimal number of links required by a k-connected graph, leading to minimal flooding cost. the paper formally shows, in particular, that there are an infinite number of pairs (n,k), such that there exists a k-regular lhg for the pair (n,k) that satisfies k-diamond and does not satisfy k-pasted-tree.
computational complexity of computing a partial solution for the graph automorphism problems. it is known that a nontrivial automorphism on a given graph is computed by using any oracle that computes a pair of vertices (u,v) such that u is mapped to v by some nontrivial automorphism. in this paper, we consider a weaker oracle acting as follows. for a given graph, the oracle returns a pair (v,b) of a vertex v and a bit b@?{0,1} with the promise that if it returns (v,0), then the vertex v is fixed by some nontrivial automorphism, but if it returns (v,1), then the vertex v is moved by some nontrivial automorphism, provided that the given graph has a nontrivial automorphism. we here note that the oracle may return an arbitrary pair as its answer in case that the given graph has no nontrivial automorphism. we then show a stronger result that such an oracle is still powerful enough to compute a nontrivial automorphism. we also show that a similar result holds for rightga, a ga-complete problem. we further investigate the computational complexity of computing a partial solution for prefixga which is known to be gi-complete. for this problem, we show that, when we consider any oracle similar to one mentioned above, the oracle does not help us to solve prefixga unless gi @?"t^p ga.
a generalization of cobham's theorem to automata over real numbers. this article studies the expressive power of finite-state automata recognizing sets of real numbers encoded positionally. it is known that the sets that are definable in the first-order additive theory of real and integer variables can all be recognized by weak deterministic buchi automata, regardless of the encoding base r>1. in this article, we prove the reciprocal property, i.e., a subset of r that is recognizable by weak deterministic automata in every base r>1 is necessarily definable in . this result generalizes to real numbers the well-known cobham's theorem on the finite-state recognizability of sets of integers. our proof gives interesting insight into the internal structure of automata recognizing sets of real numbers, which may lead to efficient data structures for handling these sets.
affine systems of equations and counting infinitary logic. we study the definability of constraint satisfaction problems (csps) in various fixed-point and infinitary logics. we show that testing the solvability of systems of equations over a finite abelian group, a tractable csp that was previously known not to be definable in datalog, is not definable in the infinitary logic with finitely many variables and counting. this implies that it is not definable in least fixed-point logic or its extension with counting. we relate definability of csps to their classification obtained from tame congruence theory of the varieties generated by the algebra of polymorphisms of the template structure. in particular, we show that if this variety admits either the unary or affine type, the corresponding csp is not definable in the infinitary logic with counting.
the 4-way deterministic tiling problem is undecidable. it is shown that the (infinite) tiling problem by wang tiles is undecidable even if the given tile set is deterministic by all four corners, i.e. a tile is uniquely determined by the colors of any two adjacent edges. the reduction is done from the turing machine halting problem and uses the aperiodic tile set of kari and papasoglu.
pictures worth a thousand tiles, a geometrical programming language for self-assembly. we present a novel way to design self-assembling systems using a notion of signal (or ray) akin to what is used in analyzing the behaviour of cellular automata. this allows purely geometrical constructions, with a smaller specification and easier analysis. we show how to design a system of signals for a given set of shapes, and how to transform these signals into a set of tiles which self-assemble into the desired shapes. we show how to use this technique on two examples: squares (with optimal assembly time and a small number of tiles) and general polygons with arbitrarily good resolution.
optimal construction of k-nearest-neighbor graphs for identifying noisy clusters. we study clustering algorithms based on neighborhood graphs on a random sample of data points. the question we ask is how such a graph should be constructed in order to obtain optimal clustering results. which type of neighborhood graph should one choose, mutual k-nearest-neighbor or symmetric k-nearest-neighbor? what is the optimal parameter k? in our setting, clusters are defined as connected components of the t-level set of the underlying probability distribution. clusters are said to be identified in the neighborhood graph if connected components in the graph correspond to the true underlying clusters. using techniques from random geometric graph theory, we prove bounds on the probability that clusters are identified successfully, both in a noise-free and in a noisy setting. those bounds lead to several conclusions. first, k has to be chosen surprisingly high (rather of the order n than of the order logn) to maximize the probability of cluster identification. secondly, the major difference between the mutual and the symmetric k-nearest-neighbor graph occurs when one attempts to detect the most significant cluster only.
coordination mechanisms for selfish scheduling. in machine scheduling, a set of jobs must be scheduled on a set of machines so as to minimize some global objective function, such as the makespan, which we consider in this paper. in practice, jobs are often controlled by independent, selfishly acting agents, which each select a machine for processing that minimizes the (expected) completion time. this scenario can be formalized as a game in which the players are job owners, the strategies are machines, and a player's disutility is the completion time of its jobs in the corresponding schedule. the equilibria of these games may result in larger-than-optimal overall makespan. the price of anarchy is the ratio of the worst-case equilibrium makespan to the optimal makespan. in this paper, we design and analyze scheduling policies, or coordination mechanisms, for machines which aim to minimize the price of anarchy of the corresponding game. we study coordination mechanisms for four classes of multiprocessor machine scheduling problems and derive upper and lower bounds on the price of anarchy of these mechanisms. for several of the proposed mechanisms, we also prove that the system converges to a pure-strategy nash equilibrium in a linear number of rounds. finally, we note that our results are applicable to several practical problems arising in communication networks.
online scheduling on two uniform machines to minimize the makespan. we consider two problems of online scheduling on two uniform machines: online scheduling under a grade of service (gos) and online scheduling with reassignment. these problems are online in the sense that when a job presents, we have to irrevocably assign it to one of the machines before the next job is seen. the objective is to minimize the makespan. in the first problem, gos means that some jobs have to be processed by some machine so that they can be guaranteed a higher quality. assume that the speed of the higher gos machine is normalized to 1, while the speed of the other one is s. we show that a lower bound of competitive ratio is 1+2ss+2 in the case 01. then we propose and analyze two online algorithms: hsf algorithm and ex-online algorithm. hsf is optimal in the case where s>1 and @s"1>=@s"2s, where @s"1 and @s"2 denote the total processing time of jobs which request higher gos machine and the total processing time of jobs which request the normal one, respectively. ex-online is optimal in the case 2(2-1)@?s@?1. in the second problem, we study two subproblems p"l and p"a proposed in [z. tan, s. yu, online scheduling with reassignment, operations research letters 36 (2008) 250-254]. assume that the speeds of 2 uniform machines are 1 and s>=1, respectively. for p"l where we can reassign the last k jobs of the sequence, we show a lower bound of competitive ratio 1+11+s. for p"a where we can reassign arbitrary k jobs, we show a lower bound of competitive ratio (s+1)^2s^2+s+1. we propose a s+1s-competitive algorithm hsf-1 for both p"l and p"a. for p"a, we propose a (s+1)^2s+2-competitive algorithm ex-ra, which is superior to hsf-1 when 1@?s@?2.
dynamic mechanism design. in this paper we address the question of designing truthful mechanisms for solving optimization problems on dynamic graphs with selfish edges. more precisely, we are given a graph g of n nodes, and we assume that each edge of g is owned by a selfish agent. the strategy of an agent consists in revealing to the system-at each time instant-the cost at the actual time for using its edge. additionally, edges can enter into and exit from g. among the various possible assumptions which can be made to model how this edge-cost modifications take place, we focus on two settings: (i) the dynamic, in which modifications can happen at any time, and for a given optimization problem on g, the mechanism has to maintain efficiently the output specification and the payment scheme for the agents; (ii) the time-sequenced, in which modifications happens at fixed time steps, and the mechanism has to minimize an objective function which takes into consideration both the quality and the set-up cost of a new solution. in both settings, we investigate the existence of exact and approximate truthful (w.r.t. to suitable equilibrium concepts) mechanisms. in particular, for the dynamic setting, we analyze the minimum spanning tree problem, and we show that if edge costs can only decrease and each agent adopts a myopic best response strategy (i.e., its utility is only measured instantaneously), then there exists an efficient dynamic truthful (in myopic best response equilibrium) mechanism for handling a sequence of k declarations of edge-cost reductions having runtime o((h+k)logn), where h is the overall number of payment changes.
efficient approximation of min set cover by moderately exponential algorithms. we study the approximation of min set cover combining ideas and results from polynomial approximation and from exact computation (with non-trivial worst case complexity upper bounds) for np-hard problems. we design approximation algorithms for min set cover achieving ratios that cannot be achieved in polynomial time (unless problems in np could be solved by slightly super-polynomial algorithms) with worst-case complexity much lower (though super-polynomial) than those of an exact computation.
perfectly quilted rectangular snake tilings. we introduce a particular form of snake tilings to define picture languages, and relate the obtained family to the recognizable picture languages (as defined by wang tiles). the correspondence for substitution tilings is even closer, and hence is applicable to the hilbert curve.
pure nash equilibria in player-specific and weighted congestion games. unlike standard congestion games, weighted congestion games and congestion games with player-specific delay functions do not necessarily possess pure nash equilibria. it is known, however, that there exist pure equilibria for both of these variants in the case of singleton congestion games, i.e., if the players' strategy spaces contain only sets of cardinality one. in this paper, we investigate how far such a property on the players' strategy spaces guaranteeing the existence of pure equilibria can be extended. we show that both weighted and player-specific congestion games admit pure equilibria in the case of matroid congestion games, i.e., if the strategy space of each player consists of the bases of a matroid on the set of resources. we also show that the matroid property is the maximal property that guarantees pure equilibria without taking into account how the strategy spaces of different players are interweaved. additionally, our analysis of player-specific matroid congestion games yields a polynomial time algorithm for computing pure equilibria. we also address questions related to the convergence time of such games. for player-specific matroid congestion games, in which the best response dynamics may cycle, we show that from every state there exists a short sequences of better responses to an equilibrium. for weighted matroid congestion games, we present a superpolynomial lower bound on the convergence time of the best response dynamics showing that players do not even converge in pseudopolynomial time.
the simultaneous consecutive ones problem. the standard consecutive ones problem is concerned with permuting the columns of a 0/1-matrix in such a way that in every row all 1-entries occur consecutively. in this paper we study this problem with the additional requirement that also in every column the 1-entries have to be consecutive. to achieve this column permutations have to be allowed as well. we show that the weighted simultaneous consecutive ones problem is np-hard and consider two special cases with fixed row and column permutations where one is still np-hard and the other one turns out to be easy.
quasi-linear transformations and discrete tilings. tilings of the discrete plane z^2 generated by quasi-linear transformations (qlt) have been introduced by nehlig [p. nehlig, applications quasi-affines: pavages par images reciproques, theoretical computer science 156 (1995) 1-38]. we studied these tilings and gave some results, such as periodicity and the number of neighbours of each of them [m.-a. jacob-da col, applications quasi-affines et pavages du plan discret, theoretical computer science 259 (2001) 245-269. also available in english: http://dpt-info.u-strasbg.fr/~jacob/articles/paving.pdf]. the aim of this paper is to go on with this study in the discrete n-dimensional space z^2; we give a lower and an upper bound to the number of distinct tiles. we also give an algorithm to determine the points of a given tile, this algorithm will induce another algorithm to determine the number of distinct tiles associated to a qlt.
maximal infinite-valued constraint languages. we systematically investigate the computational complexity of constraint satisfaction problems for constraint languages over an infinite domain. in particular, we study a generalization of the well-established notion of maximal constraint languages from finite to infinite domains. if the constraint language can be defined with an @w-categorical structure, then maximal constraint languages are in one-to-one correspondence to minimal oligomorphic clones. based on this correspondence, we derive general tractability and hardness criteria for the corresponding constraint satisfaction problems.
a constructive borel-cantelli lemma. constructing orbits with required statistical properties. in the general context of computable metric spaces and computable measures we prove a kind of constructive borel-cantelli lemma: given a sequence (constructive in some way) of sets a"i with effectively summable measures, there are computable points which are not contained in infinitely many a"i. as a consequence of this we obtain the existence of computable points which follow the typical statistical behavior of a dynamical system (they satisfy the birkhoff theorem) for a large class of systems, having computable invariant measure and a certain ''logarithmic'' speed of convergence of birkhoff averages over lipschitz observables. this is applied to uniformly hyperbolic systems, piecewise expanding maps, systems on the interval with an indifferent fixed point and it directly implies the existence of computable numbers which are normal with respect to any base.
improved constructions of quantum automata. we present a simple construction of quantum automata which achieve an exponential advantage over classical finite automata. our automata use 4@elog2p states to recognize a language that requires p states classically. the construction is both substantially simpler and achieves a better constant in the front of logp than the previously known construction. our construction is by a probabilistic argument. we consider the possibility to derandomize it and present some results in this direction.
morphically primitive words. in the present paper, we introduce an alternative notion of the primitivity of words, that-unlike the standard understanding of this term-is not based on the power (and, hence, the concatenation) of words, but on morphisms. for any alphabet @s, we call a word w@?@s^*morphically imprimitive provided that there are a shorter word v and morphisms h,h^':@s^*->@s^* satisfying h(v)=w and h^'(w)=v, and we say that w is morphically primitive otherwise. we explain why this is a well-chosen terminology, we demonstrate that morphic (im-) primitivity of words is a vital attribute in many combinatorial domains based on finite words and morphisms, and we study a number of fundamental properties of the concepts under consideration.
approximation hardness of deadline-tsp reoptimization. given an instance of an optimization problem together with an optimal solution, we consider the scenario in which this instance is modified locally. in graph problems, e.g., a singular edge might be removed or added, or an edge weight might be varied, etc. for a problem u and such a local modification operation, let lm-u (local-modification-u) denote the resulting problem. the question is whether it is possible to exploit the additional knowledge of an optimal solution to the original instance or not, i.e.,whether lm-u is computationally more tractable than u. while positive examples are known e.g. for metric tsp, we give some negative examples here: metric tsp with deadlines (time windows), if a single deadline or the cost of a single edge is modified, exhibits the same lower bounds on the approximability in these local-modification versions as those currently known for the original problem.