waashk/dblp huggingface dataset:
equilibria of atomic flow games are not unique. in routing games with infinitesimal players, it follows from well-known convexity arguments that equilibria exist and are unique (up to induced delays, and under weak assumptions on delay functions). in routing games with players that control large amounts of flow, uniqueness has been demonstrated only in limited cases: in 2-terminal, nearly-parallel graphs; when all players control exactly the same amount of flow; when latency functions are polynomials of degree at most three. in this work, we answer an open question posed by cominetti, correa, and stier-moses (icalp 2006) and show that there may be multiple equilibria in atomic player routing games. we demonstrate this multiplicity via two specific examples. in addition, we show our examples are topologically minimal by giving a complete characterization of the class of network topologies for which unique equilibria exist. our proofs and examples are based on a novel characterization of these topologies in terms of sets of circulations.
on the approximability of dodgson and young elections. the voting rules proposed by dodgson and young are both designed to find the alternative closest to being a condorcet winner, according to two different notions of proximity; the score of a given alternative is known to be hard to compute under either rule. in this paper, we put forward two algorithms for approximating the dodgson score: an lp-based randomized rounding algorithm and a deterministic greedy algorithm, both of which yield an o(log m) approximation ratio, where m is the number of alternatives; we observe that this result is asymptotically optimal, and further prove that our greedy algorithm is optimal up to a factor of 2, unless problems in np have quasi-polynomial time algorithms. although the greedy algorithm is computationally superior, we argue that the randomized rounding algorithm has an advantage from a social choice point of view. further, we demonstrate that computing any reasonable approximation of the ranking produced by dodgson's rule is np-hard. this result provides a complexity-theoretic explanation of sharp discrepancies that have been observed in the social choice theory literature when comparing dodgson elections with simpler voting rules. finally, we show that the problem of calculating the young score is np-hard to approximate by any factor. this leads to an inapproximability result for the young ranking.
expanders via random spanning trees. motivated by the problem of routing reliably and scalably in a graph, we introduce the notion of a splicer, the union of spanning trees of a graph. we prove that for any bounded-degree n-vertex graph, the union of two random spanning trees approximates the expansion of every cut of the graph to within a factor of o(log n). for the random graph gn, p, for p = &omega;(log n/n), we give a randomized algorithm for constructing two spanning trees whose union is an expander. this is suggested by the case of the complete graph, where we prove that two random spanning trees give an expander. the construction of the splicer is elementary; each spanning tree can be produced independently using an algorithm by aldous and broder: a random walk in the graph with edges leading to previously unvisited vertices included in the tree. splicers also turn out to have applications to graph cut-sparsification where the goal is to approximate every cut using only a small subgraph of the original graph. for random graphs, splicers provide simple algorithms for sparsifiers of size o(n) that approximate every cut to within a factor of o(log n).
perfect matchings via uniform sampling in regular bipartite graphs. in this article we further investigate the well-studied problem of finding a perfect matching in a regular bipartite graph. the first nontrivial algorithm, with running time o(mn), dates back to k&ouml;nig's work in 1916 (here m&equals;nd is the number of edges in the graph, 2n is the number of vertices, and d is the degree of each node). the currently most efficient algorithm takes time o(m), and is due to cole et al. &lsqb;2001&rsqb;. we improve this running time to o(min{m, n2.5ln n/d}); this minimum can never be larger than o(n1.75&sqrt;ln n). we obtain this improvement by proving a uniform sampling theorem: if we sample each edge in a d-regular bipartite graph independently with a probability p &equals; o(n ln n/d2) then the resulting graph has a perfect matching with high probability. the proof involves a decomposition of the graph into pieces which are guaranteed to have many perfect matchings but do not have any small cuts. we then establish a correspondence between potential witnesses to nonexistence of a matching (after sampling) in any piece and cuts of comparable size in that same piece. karger's sampling theorem &lsqb;1994a, 1994b&rsqb; for preserving cuts in a graph can now be adapted to prove our uniform sampling theorem for preserving perfect matchings. using the o(m&sqrt;n) algorithm (due to hopcroft and karp &lsqb;1973&rsqb;) for finding maximum matchings in bipartite graphs on the sampled graph then yields the stated running time. we also provide an infinite family of instances to show that our uniform sampling result is tight up to polylogarithmic factors (in fact, up to ln2 n).
approximate euclidean shortest paths amid convex obstacles. we develop algorithms and data structures for the approximate euclidean shortest path problem amid a set p of k convex obstacles in r2 and r3, with a total of n faces. the running time of our algorithms is linear in n, and the size and query time of our data structure are independent of n. we follow a "core-set" based approach, i.e., we quickly compute a small sketch q of p whose size is independent of n and then compute approximate shortest paths with respect to q.
list-color-critical graphs on a fixed surface. a k-list-assignment for a graph g assigns to each vertex v of g a list l(v) of admissible colors, where |l(v)| &ge; k. a graph is k-list-colorable (or k-choosable) if it can be properly colored from the lists for every k-list-assignment. we prove the following conjecture posed by thomassen in 1994: "there are only finitely many list-color-critical graphs with all lists of cardinality at least 5 on any fixed surface." this generalizes the well-known result of thomassen on the usual graph coloring case. we use this theorem and specific parts of its proof to resolve the complexity status of the following problem about k-list-coloring graphs on a fixed surface s, where k is a fixed positive integer. input: a graph g embedded in the surface s. question: is g k-choosable? if not, provide a certificate (a list-color-critical subgraph and the corresponding k-list-assignment). the cases k = 3, 4 are known to be np-hard (actually even &pi;p2-complete), and the cases k = 1, 2 are easy. our main results imply that the problem is tractable for every k &ge; 5. in fact, together with our recent algorithmic result, we are able to solve it in linear time when k &ge; 5. our proof yields even more: if the input graph is k-list-colorable, then for any k-list-assignment l, we can construct an l-coloring of g in linear time. this generalizes the well-known linear-time algorithms for planar graphs by nishizeki and chiba (for 5-coloring), and thomassen (for 5-list-coloring). we also give a polynomial-time algorithm to resolve the following question: input: a graph g in the surface s, and a k-list-assignment l, where k &ge; 5. question: does g admit an l-coloring? if not, provide a certificate for this. if yes, then return an l-coloring. if the graph g is k-list-colorable, then our first result gives a linear time solution. however, the second problem is more general, since it provides a coloring (or a small obstruction) for an arbitrary graph in s. we also use our main theorem to prove another conjecture that was proposed recently by thomassen: "for every fixed surface s, there exists a positive constant c such that every 5-list-colorable graph with n vertices embedded on s, has at least c &middot; 2n distinct 5-list-colorings for every 5-list-assignment for g." thomassen himself proved that this conjecture holds for usual 5-colorings. in addition to all these results, we also made partial progress towards a conjecture of albertson concerning coloring extensions and a progress on similar questions for triangle-free graphs and graphs of larger girth.
on the relative strength of split, triangle and quadrilateral cuts. integer programs defined by two equations with two free integer variables and nonnegative continuous variables have three types of nontrivial facets: split, triangle or quadrilateral inequalities. in this paper, we compare the strength of these three families of inequalities. in particular we study how well each family approximates the integer hull. we show that, in a well defined sense, triangle inequalities provide a good approximation of the integer hull. the same statement holds for quadrilateral inequalities. on the other hand, the approximation produced by split inequalities may be arbitrarily bad.
discounted deterministic markov decision processes and discounted all-pairs shortest paths. we present algorithms for finding optimal strategies for discounted, infinite-horizon, determinsitc markov decision processes (dmdps). our fastest algorithm has a worst-case running time of o(mn), improving the recent bound of o(mn2) obtained by andersson and vorbyov &lsqb;2006&rsqb;. we also present a randomized o(m1/2n2)-time algorithm for finding discounted all-pairs shortest paths (dapsp), improving an o(mn2)-time algorithm that can be obtained using ideas of papadimitriou and tsitsiklis &lsqb;1987&rsqb;.
online story scheduling in web advertising. we study an online job scheduling problem motivated by storyboarding in web advertising, where an advertiser derives value from uninterrupted sequential access to a user surfing the web. the user ceases to browse with probability 1 -- &beta; at each step, independently. stories (jobs) arrive online; job s has length ls and per-unit value vs. a value vs is obtained for every unit of the job that is scheduled consecutively without interruption, discounted for the time at which it is scheduled. jobs can be preempted, but no further value can be derived from the residual unscheduled units of the job. we seek an online algorithm whose total reward is competitive against that of the offline scheduler that knows all jobs in advance. we consider two models based on the maximum delay that can be allowed between the arrival and scheduling of a job. in the first, a job can be scheduled anytime after its arrival; in the second a job is lost unless scheduled immediately upon arrival, preempting a currently running job if needed. the two settings correspond to two natural models of how long an advertiser retains interest in a relevant user. we show that there is, in fact, a sharp separation between what an online scheduler can achieve in these two settings. in the first setting with no deadlines, we give a natural deterministic algorithm with a constant competitive ratio against the offline scheduler. in contrast, we show that in the sharp deadline setting, no (deterministic or randomized) online algorithm can achieve better than a polylogarithmic ratio.
maximal biconnected subgraphs of random planar graphs. let c be a class of labeled connected graphs, and let cn be a graph drawn uniformly at random from graphs in c that contain exactly n vertices. denote by b(&ell;; cn) the number of blocks (i.e., maximal biconnected subgraphs) of cn that contain exactly &ell; vertices, and let lb(cn) be the number of vertices in a largest block of cn. we show that under certain general assumptions on c, cn belongs with high probability to one of the following categories: (1) lb(cn) &sim; cn, for some explicitly given c &equals; c(c), and the second largest block is of order n&alpha;, where 1 > &alpha; &equals; &alpha;(c), or (2) lb(cn) &equals; o(log n), that is, all blocks contain at most logarithmically many vertices. moreover, in both cases we show that the quantity b(&ell;; cn) is concentrated for all &ell; and we determine its expected value. as a corollary we obtain that the class of planar graphs belongs to category (1). in contrast to that, outerplanar and series-parallel graphs belong to category (2).
optimal halfspace range reporting in three dimensions. we give the first optimal solution to a standard problem in computational geometry: three-dimensional halfspace range reporting. we show that n points in 3-d can be stored in a linear-space data structure so that all k points inside a query halfspace can be reported in o(log n + k) time. the data structure can be built in o(n log n) expected time. the previous methods with optimal query time required superlinear (o(n log log n)) space. we also mention consequences, for example, to higher dimensions and to external-memory data structures. as an aside, we partially answer another open question concerning the crossing number in matou&scaron;ek's shallow partition theorem in the 3-d case (a tool used in many known halfspace range reporting methods).
improved smoothed analysis of the -means method. the k-means method is a widely used clustering algorithm. one of its distinguished features is its speed in practice. its worst-case running-time, however, is exponential, leaving a gap between practical and theoretical performance. arthur and vassilvitskii [3] aimed at closing this gap, and they proved a bound of poly(nk, &sigma;&minus;1) on the smoothed running-time of the k-means method, where n is the number of data points and &sigma; is the standard deviation of the gaussian perturbation. this bound, though better than the worst-case bound, is still much larger than the running-time observed in practice. we improve the smoothed analysis of the k-means method by showing two upper bounds on the expected running-time of k-means. first, we prove that the expected running-time is bounded by a polynomial in n&radic;k and &sigma;&minus;1. second, we prove an upper bound of kkd&middot;poly(n, &sigma;&minus;1), where d is the dimension of the data space. the polynomial is independent of k and d, and we obtain a polynomial bound for the expected running-time for k, d &isin; o(&radic;logn/log logn). finally, we show that k-means runs in smoothed polynomial time for one-dimensional instances.
sorting and selection in posets. classical problems of sorting and searching assume an underlying linear ordering of the objects being compared. in this paper, we study these problems in the context of partially ordered sets, in which some pairs of objects are incomparable. this generalization is interesting from a combinatorial perspective, and it has immediate applications in ranking scenarios where there is no underlying linear ordering, e.g., conference submissions. it also has applications in reconstructing certain types of networks, including biological networks. our results represent significant progress over previous results from two decades ago by faigle and tur&aacute;n. in particular, we present the first algorithm that sorts a width-w poset of size n with optimal query complexity o(n(w + log n)). we also describe a variant of mergesort with query complexity o(wn log n/w) and total complexity o(w2n log n/w); an algorithm with the same query complexity was given by faigle and tur&aacute;n, but no efficient implementation of that algorithm is known. both our sorting algorithms can be applied with negligible overhead to the more general problem of reconstructing transitive relations. we also consider two related problems: finding the minimal elements, and its generalization to finding the bottom k "levels", called the k-selection problem. we give efficient deterministic and randomized algorithms for finding the minimal elements with o(wn) query and total complexity. we provide matching lower bounds for the query complexity up to a factor of 2 and generalize the results to the k-selection problem. finally, we present efficient algorithms for computing a linear extension of a poset and computing the heights of all elements.
better algorithms for benign bandits. the online multi-armed bandit problem and its generalizations are repeated decision making problems, where the goal is to select one of several possible decisions in every round, and incur a cost associated with the decision, in such a way that the total cost incurred over all iterations is close to the cost of the best fixed decision in hindsight. the difference in these costs is known as the regret of the algorithm. the term bandit refers to the setting where one only obtains the cost of the decision used in a given iteration and no other information. perhaps the most general form of this problem is the non-stochastic bandit linear optimization problem, where the set of decisions is a convex set in some euclidean space, and the cost functions are linear. only recently an efficient algorithm attaining &otilde; (&radic;t) regret was discovered in this setting. in this paper we propose a new algorithm for the bandit linear optimization problem which obtains a regret bound of &otilde; (&radic;q), where q is the total variation in the cost functions. this regret bound, previously conjectured to hold in the full information case, shows that it is possible to incur much less regret in a slowly changing environment even in the bandit setting. our algorithm is efficient and applies several new ideas to bandit optimization such as reservoir sampling.
additive approximation algorithms for list-coloring minor-closed class of graphs. it is known that computing the list chromatic number is harder than computing the chromatic number (assuming np &ne; conp). in fact, the problem of deciding whether a given graph is f-list-colorable for a function f: v &rarr; {c -1, c} for c &ge; 3 is &pi;p2-complete. in general, it is believed that approximating list coloring is hard for dense graphs. in this paper, we are interested in sparse graphs. more specifically, we deal with nontrivial minor-closed classes of graphs, i.e., graphs excluding some kk minor. we refine the seminal structure theorem of robertson and seymour, and then give an additive approximation for list-coloring within k - 2 of the list chromatic number. this improves the previous multiplicative o(k)-approximation algorithm [20]. clearly our result also yields an additive approximation algorithm for graph coloring in a minor-closed graph class. this result may give better graph colorings than the previous multiplicative 2-approximation algorithm for graph coloring in a minor-closed graph class [6]. our structure theorem is of independent interest in the sense that it gives rise to a new insight on well-connected h-minor-free graphs. in particular, this class of graphs can be easily decomposed into two parts so that one part has bounded treewidth and the other part is a disjoint union of bounded-genus graphs. moreover, we can control the number of edges between the two parts. the proof method itself tells us how knowledge of a local structure can be used to gain a global structure, which gives new insight on how to decompose a graph with the help of local-structure information.
shortest paths in directed planar graphs with negative lengths: a linear-space ( log )-time algorithm. we give an o(n log2 n)-time, linear-space algorithm that, given a directed planar graph with positive and negative arc-lengths, and given a node s, finds the distances from s to all nodes.
dual-failure distance and connectivity oracles. spontaneous failure is an unavoidable aspect of all networks, particularly those with a physical basis such as communications networks or road networks. whether due to malicious coordinated attacks or other causes, failures temporarily change the topology of the network and, as a consequence, its connectivity and distance metric. in this paper we look at the problem of efficiently answering connectivity, distance, and shortest route queries in the presence of two node or link failures. our data structure uses &otilde;(n2) space and answers queries in &otilde; (1) time, which is within a polylogarithmic factor of optimal and nearly matches the single-failure distance oracles of demestrescu et al. it may yet be possible to find distance/connectivity oracles capable of handling any fixed number of failures. however, the sheer complexity of our algorithm suggests that moving beyond dual-failures will require a fundamentally different approach to the problem.
three-coloring triangle-free planar graphs in linear time. gr&ouml;tzsch's theorem states that every triangle-free planar graph is 3-colorable, and several relatively simple proofs of this fact were provided by thomassen and other authors. it is easy to convert these proofs into quadratic-time algorithms to find a 3-coloring, but it is not clear how to find such a coloring in linear time (kowalik used a nontrivial data structure to construct an o(n log n) algorithm). we design a linear-time algorithm to find a 3-coloring of a given triangle-free planar graph. the algorithm avoids using any complex data structures, which makes it easy to implement. as a by-product we give a yet simpler proof of gr&ouml;tzsch's theorem.
pairing heaps with (log log ) decrease cost. we give a variation of the pairing heaps for which the time bounds for all the operations match the lower bound proved by fredman for a family of similar self-adjusting heaps. namely, our heap structure requires o(1) for insert and findmin, o(log n) for delete-min, and o(log log n) for decrease-key and meld (all the bounds are in the amortized sense except for find-min).
fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths. given a directed graph with a capacity on each edge, the all-pairs bottleneck paths (apbp) problem is to determine, for all vertices s and t, the maximum flow that can be routed from s to t. for dense graphs this problem is equivalent to that of computing the (max, min)-transitive closure of a real-valued matrix. in this paper, we give a (max, min)-matrix multiplication algorithm running in time o(n(3+&omega;)/2) &le; o(n2.688), where &omega; is the exponent of binary matrix multiplication. our algorithm improves on a recent o(n2+&omega;/3) &le; o(n2.792)- time algorithm of vassilevska, williams, and yuster. although our algorithm is slower than the best apbp algorithm on vertex capacitated graphs, running in o(n2.575) time, it is just as efficient as the best algorithm for computing the dominance product, a problem closely related to (max, min)-matrix multiplication. our techniques can be extended to give subcubic algorithms for related bottleneck problems. the all-pairs bottleneck shortest paths problem (apbsp) asks for the maximum flow that can be routed along a shortest path. we give an apbsp algorithm for edge-capacitated graphs running in o(n(3+&omega;)/2) time and a slightly faster o(n2.657)-time algorithm for vertex-capactitated graphs. the second algorithm significantly improves on an o(n2.859)-time apbsp algorithm of shapira, yuster, and zwick. our apbsp algorithms make use of new hybrid products we call the distance-max-min product and dominance-distance product.
a simple combinatorial algorithm for submodular function minimization. this paper presents a new simple algorithm for minimizing submodular functions. for integer valued submodular functions, the algorithm runs in o(n6eo log nm) time, where n is the cardinality of the ground set, m is the maximum absolute value of the function value, and eo is the time for function evaluation. the algorithm can be improved to run in o ((n4eo+n5)log nm) time. the strongly polynomial version of this faster algorithm runs in o((n5eo + n6) log n) time for real valued general submodular functions. these are comparable to the best known running time bounds for submodular function minimization. the algorithm can also be implemented in strongly polynomial time using only additions, subtractions, comparisons, and the oracle calls for function evaluation. this is the first fully combinatorial submodular function minimization algorithm that does not rely on the scaling method.