waashk/dblp huggingface dataset:
robust algorithms for restricted domains. we introduce a new definition of efficient algorithms for restricted domains. under this definition, an algorithm is required to be "robust," i.e., it must produce correct output regardless of whether the input actually belongs to the restricted domain or not. this is to be contrasted with the "promise" version of solving problems on restricted domains, in which there is a guarantee that the input is in the class, and an algorithm to "solve" the problem need not function correctly or even terminate if this guarantee is not met. there exist problems that have a polynomial time promise solution, while being np-hard if required to be robust. we show perhaps the surprising result that robustly finding a maximum independent set in a well-covered graph (i.e., a graph in which every maximal independent set is of the same size) is np-hard. an argument can be made that this hardness result is more meaningful than the trivial polynomial time promise algorithm. we give a polynomial time robust algorithm for the maximum clique problem in unit disk graphs, i.e., given an input graph g in general form, the output is either a maximum clique for g or a certificate that g is not a unit disk graph. the existence of this algorithm is to be reconciled with the apparent contradiction posed by the facts: (1) recognizing whether an input graph given in general form is a unit disk graph is np-hard; in fact, it is not even known to be in np. (2) finding a maximum clique in an input graph given in general form is np-hard.
pursuit-evasion with imprecise target location. we consider a game between two persons where one person tries to chase the other, but the pursuer only knows an approximation of the true position of the fleeing person. the two players have identical constraints on their speed. it turns out that the fugitive can increase his distance from the pursuer beyond any limit. however, when the speed constraints are given by a polyhedral metric, the pursuer can always remain within a constant distance of the other person.we apply this problem to buffer minimization in an online scheduling problem with conflicts.
improved approximation bound for quadratic optimization problems with orthogonality constraints. in this paper we consider the problem of approximating a class of quadratic optimization problems that contain orthogonality constraints, i.e. constraints of the form xtx = i, where x &epsilon; rm x n is the optimization variable. this class of problems, which we denote by (qp--oc), is quite general and captures several well--studied problems in the literature as special cases. in a recent work, nemirovski [17] gave the first non--trivial approximation algorithm for (qp--oc). his algorithm is based on semidefinite programming and has an approximation guarantee of o ((m + n)1/3). we improve upon this result by providing the first logarithmic approximation guarantee for (qp--oc). specifically, we show that (qp--oc) can be approximated to within a factor of o(ln (max{m, n})). the main technical tool used in the analysis is the so--called non--commutative khintchine inequality, which allows us to prove a concentration inequality for the spectral norm of a rademacher sum of matrices. as a by-product, we resolve in the affirmative a conjecture of nemirovski concerning the typical spectral norm of a sum of certain random matrices. the aforementioned concentration inequality also has ramifications in the design of so-called safe tractable approximations of chance constrained optimization problems. in particular, we use it to simplify and improve a recent result of ben--tal and nemirovski [4] concerning certain chance constrained linear matrix inequality systems.
region-fault tolerant geometric spanners. we introduce the concept of region-fault tolerant spanners for planar point sets and prove the existence of region-fault tolerant spanners of small size. for a geometric graph $\mathcal{g}$on a point set p and a region&#x00a0;f, we define $\mathcal{g}\ominus f$to be what remains of $\mathcal{g}$after the vertices and edges of $\mathcal{g}$intersecting&#x00a0;f have been removed. a&#x00a0; $\mathcal{c}$-fault tolerant t-spanner is a geometric graph&#x00a0; $\mathcal{g}$on&#x00a0;p such that for any convex region&#x00a0;f, the graph $\mathcal{g}\ominus f$is a t-spanner for $\mathcal{g}_{c}(p)\ominus f$, where $\mathcal{g}_{c}(p)$is the complete geometric graph on p. we prove that any set&#x00a0;p of n points admits a $\mathcal{c}$-fault tolerant (1+&#x03b5;)-spanner of size $\mathcal{o}(n\log n)$for any constant &#x03b5;>0; if adding steiner points is allowed, then the size of the spanner reduces to&#x00a0; $\mathcal{o}(n)$, and for several special cases, we show how to obtain region-fault tolerant spanners of $\mathcal{o}(n)$size without using steiner points. we also consider fault-tolerant geodesic t -spanners: this is a variant where, for any disk&#x00a0;d, the distance in $\mathcal{g}\ominus d$between any two points u,v&#x2208;p&#x2216;d is at most&#x00a0;t times the geodesic distance between u and v in &#x211d;2&#x2216;d. we prove that for any&#x00a0;p, we can add $\mathcal{o}(n)$steiner points to obtain a fault-tolerant geodesic (1+&#x03b5;)-spanner of size&#x00a0; $\mathcal{o}(n)$.
compressed counting. we propose compressed counting (cc) for approximating the &alpha;th frequency moments (0 < &alpha; &le; 2) of data streams under a relaxed strict-turnstile model, using maximally-skewed stable random projections. estimators based on the geometric mean and the harmonic mean are developed. when &alpha; = 1, a simple counter suffices for counting the first moment (i.e., sum). the geometric mean estimator of cc has asymptotic variance &alpha; &delta; = |&alpha; - 1|, capturing the intuition that the complexity should decrease as &delta; = |&alpha; - 1| &rarr; 0. however, the previous classical algorithms based on symmetric stable random projections[12, 15] required o (1/&epsilon;2) space, in order to approximate the &alpha;th moments within a 1 + &epsilon; factor, for any 0 < &alpha; &le; 2 including &alpha; = 1. we show that using the geometric mean estimator, cc requires o [equation] space, as &delta; &rarr; 0. therefore, in the neighborhood of &alpha; = 1, the complexity of cc is essentially o (1/&epsilon;) instead of o (1/&epsilon;2). cc may be useful for estimating shannon entropy, which can be approximated by certain functions of the &alpha;th moments with &alpha; &rarr; 1. [10, 9] suggested using &alpha; = 1 + &delta; with (e.g.,) &delta; < 0.0001 and &epsilon; < 10&minus;7, to rigorously ensure reasonable approximations. thus, unfortunately, cc is "theoretically impractical" for estimating shannon entropy, despite its empirical success reported in [16].
emulations between qsm, bsp, and logp: a framework for general-purpose parallel algorithm design. we present work-preserving emulations with small slowdown between logp and two other parallel models: bsp and qsm. in conjunction with earlier work-preserving emulations between qsm and bsp, these results establish a close correspondence between these three general-purpose parallel models. our results also correct and improve on results reported earlier on emulations between bsp and logp. in particular we shed new light on the relative power of stalling and non-stalling logp models.the qsm is a shared-memory model with only two parameters--p, the number of processors, and g, a bandwidth parameter. the simplicity of the qsm parameters makes qsm a convenient model for parallel algorithm design, and simple work-preserving emulations of qsm on bsp and qsm on logp show that algorithms designed for the qsm will also map quite well to these other models. the simplicity and generality of qsm present a strong case for the use of qsm as the model of choice for parallel algorithm design.we present qsm algorithms for three basic problems--prefix sums, sample sort and list ranking. we show that these algorithms are optimal in terms of both the total work performed and the number of 'phases' for input sizes of practical interest. for prefix sums, we present a matching lower bound that shows our algorithm to be optimal over the complete range of these parameters. we then examine the predicted and simulated performance of these algorithms. these results suggest that qsm analysis will predict algorithm performance quite accurately for problem sizes that arise in practice.
strictly convex drawings of planar graphs. every three-connected planar graph with n vertices has a drawing on an o(n7/3) &times; o(n7/3) grid in which all faces are strictly convex polygons.
the rectilinear steiner arborescence problem is np-complete. given a set of points in the first quadrant, a rectilinear steiner arborescence (rsa) is a directed tree rooted at the origin, containing all points, and composed solely of horizontal and vertical edges oriented from left to right, or from bottom to top. the complexity of finding an rsa with the minimum total edge length for general planar point sets has been a well-known open problem in algorithm design and vlsi routing. in this paper, we prove the problem is np-complete in the strong sense.
succinct indexable dictionaries with applications to encoding k-ary trees and multisets. we consider the indexable dictionary problem which consists in storing a set s &sube; {0,&hellip;, m - 1} for some integer m, while supporting the operations of rank(x), which returns the number of elements in s that are less than x if x &epsilon; s, and -1 otherwise; and select(i) which returns the i-th smallest element in s.we give a structure that supports both operations in o(1) time on the ram model and requires b(n,m) + o(n) + o(lg lg m) bits to store a set of size n, where b(n,m) = &lceil;lg (nm)&rceil; is the minimum number of bits required to store any n-element subset from a universe of size m. previous dictionaries taking this space only supported (yes/no) membership queries in o(1) time. in the cell probe model we can remove the o(lg lg m) additive term in the space bound, answering a question raised by fich and miltersen, and pagh.we also present two applications of our dictionary structure:&bull; an information-theoretically optimal representation for k-ary cardinal trees (aka k-ary tries). our structure uses c(n,k) + o(n + lg k) bits to store a k-ary tree with n nodes and can support parent, i-th child, child labeled i, and the degree of a node in constant time, where c(n,k) is the minimum number of bits to store any n-node k-ary tree. previous space efficient representations for cardinal k-ary trees required c(n,k) + &omega;(n) bits.&bull; an optimal representation for multisets where (appropriate generalisations of) the select and rank operations can be supported in o(1) time. our structure uses b(n, m + n) + o(n) + o(lg lg m) bits to represent a multiset of size n from an m element set; the first term is the minimum number of bits required to represent such a multiset.
facility location with service installation costs. we consider a generalization of the uncapacitated facility location problem which we call facility location with service installation costs. we are given a set of facilities, f,a set of demands or clients d, and a set of services s. each facility i has a facility opening cost fi, and we have a service installation cost of fli for every facility-service pair (i, l). each client j in d requests a specific service g(j) &isin; s and the cost of assigning a client j to facility i is given by cij. we want to open a set of facilities, install services at the open facilities, and assign each client j to an open facility at which service g(j) is installed, so as to minimize the sum of the facility opening costs, the service installation costs and the client assignment costs.our main result is a primal-dual 6-approximation algorithm under the assumption that there is an ordering on the facilities such that if i comes before i' in this ordering then for every service type l, fli &le; fl i. this includes (as special cases) the settings where the service installation cost fli depends only on the service type l, or depends only on the location i. with arbitrary service installation costs, the problem becomes as hard as the set-cover problem. our algorithm extends the algorithm of jain & vazirani [9] in a novel way. if the service installation cost depends only on the service type and not on the location, we give an lp rounding algorithm that attains an improved approximation ratio of 2.391. the algorithm combines both clustered randomized rounding [6] and the filtering based technique of [10, 14]. we also consider the k-median version of the problem where there is an additional requirement that at most k facilities may be opened. we use our primal-dual algorithm to give a constant-factor approximation for this problem when the service installation cost depends only on the service type.
improved approximation algorithms for shop scheduling problems. in the job shop scheduling problem, there are $m$ machines and $n$ jobs. a job consists of a sequence of operations, each of which must be processed on a specified machine, and the aim is to complete all jobs as quickly as possible. this problem is strongly ${\cal np}$-hard even for very restrictive special cases. the authors give the first randomized and deterministic polynomial-time algorithms that yield polylogarithmic approximations to the optimal length schedule. these algorithms also extend to the more general case where a job is given not by a linear ordering of the machines on which it must be processed but by an arbitrary partial order. comparable bounds can also be obtained when there are $m'$ types of machines, a specified number of machines of each type, and each operation must be processed on one of the machines of a specified type, as well as for the problem of scheduling unrelated parallel machines subject to chain precedence constraints.
slow mixing of glauber dynamics via topological obstructions. many local markov chains based on glauber dynamics are known to undergo a phase transition as a parameter &lambda; of the system is varied. for independent sets on the 2-dimensional cartesian lattice, the gibbs distribution assigns each independent set a weight &lambda;[i], and the markov chain adds or deletes a single vertex at each step, it is believed that there is a critical point &lambda;c &ap; 3.79 such that for &lambda; < &lambda;c, local dynamics converge in polynomial time while for &lambda; > &lambda;c they require exponential time. we introduce a new method for showing slow mixing based on the presence or absence of certain topological obstructions in the independent sets. using elementary arguments, we show that glauber dynamics will be slow for sampling independent sets in 2 dimensions when &lambda; &ge; 8.066, improving on the best known bound by a factor of 10. we also show they are slow on the torus when &lambda; &ge; 6.183.
scheduling precedence-constrained jobs with stochastic processing times on parallel machines. we consider parallel machine scheduling problems where the jobs are subject to precedence constraints, and the processing times of jobs are governed by independent probability distributions. the objective is to minimize the weighted sum of job completion times &sum;, w, c, in expectation, where w, &gne; 0. building upon an lp-relaxation from [3] and an idle time charging scheme from [1], we derive the first approximation algorithms for this model.
distributed approaches to triangulation and embedding. a number of recent papers in the networking community study the distance matrix defined by the node-to-node latencies in the internet and, in particular, provide a number of quite successful distributed approaches that embed this distance into a low-dimensional euclidean space. in such algorithms it is feasible to measure distances among only a linear or near-linear number of node pairs; the rest of the distances are simply not available. moreover, for applications it is desirable to spread the load evenly among the participating nodes. indeed, several recent studies use this 'fully distributed' approach and achieve, empirically, a low distortion for all but a small fraction of node pairs.this is concurrent with the large body of theoretical work on metric embeddings, but there is a fundamental distinction: in the theoretical approaches to metric embeddings, full and centralized access to the distance matrix is assumed and heavily used. in this paper we present the first fully distributed embedding algorithm with provable distortion guarantees for doubling metrics (which have been proposed as a reasonable abstraction of internet latencies), thus providing some insight into the empirical success of the recent vivaldi algorithm [5]. the main ingredient of our embedding algorithm is an improved fully distributed algorithm for a more basic problem of triangulation, where the triangle inequality is used to infer the distances that have not been measured; this problem received a considerable attention in the networking community, and has also been studied theoretically in [19].we use our techniques to extend &isin;-relaxed embeddings and triangulations to infinite metrics and arbitrary measures, and to improve on the approximate distance labeling scheme of talwar [33].
existence theorems, lower bounds and algorithms for scheduling to meet two objectives. we give general results about the existence of schedules which simultaneously minimize two criteria. our results are general in that (i) they apply to any scheduling environment and (ii) they apply to all pairs of metrics in which the first metric is one of maximum flow time, makespan, or maximum lateness and the second metric is one of average flow time, average completion time, average lateness, or number of on-time jobs. for most of the pairs of metrics we consider, we show the existence of near-optimal schedules for both metrics as well as some lower bound results. for some pairs of metrics such as (maximum flow time, average weighted flow time) and (maximum flow time, number of on-time jobs), we prove negative results on the ability to approximate both criteria within a constant factor of optimal. for many other criteria we present lower bounds that match or approach our bicriterion existence results.
approximately covering by cycles in planar graphs. let g = (v(g), e(g)) be a graph and let c be the collection of its cycles. let p: e(g) &rarrtl; z+&ogr;? be a non-negative, integer-valued function on its edge set. the cycle cover problem is the optimization problem of finding a multiset a of cycles of g such that each edge e &isin; e is in at least p(e) of the cycles in a and such that the sum of the lengths of all cycles in a is minimum. we will show how to approximate within a factor of 8 the optimum value of the cycle cover problem for planar graphs in polynomial time.
on the chromatic number of some geometric hypergraphs. a finite family r of simple jordan regions in the plane defines a hypergraph h = h(r) where the vertex set of h is r and the hyperedges are all subsets s &sub; r for which there is a point p such that s = {r &isin; r|p &isin; r. the chromatic number of h(r) is the minimum number of colors needed to color the members of r such that no hyperedge is monochromatic. in this paper we initiate the study of the chromatic number of such hypergraphs. we obtain the following results:(i) any hypergraph that is induced by a family of n simple jordan regions (not necessarily convex) such that the union complexity of any m of them is given by u(m) and u(m)/m is non-decreasing is o(u(n)/n)-colorable. thus, for example we prove that any finite family of pseudodiscs can be colored with a constant number of colors.(ii) any hypergraph induced by a finite family of planar discs is four-colorable. this bound is tight. in fact, we prove that this statement is equivalent to the four-color theorem.(iii) any hypergraph induced by n axis-parallel rectangles is o(log n)-colorable. this bound is asymptotically tight.our proofs are constructive. namely, we provide deterministic polynomial-time algorithms for coloring such hypergraphs with only "few" colors (that is, the number of colors used by these algorithms is upper bounded by the same bounds we obtain on the chromatic number of the given hypergraphs)as an application of (i) and (ii) we obtain simple constructive proofs for the following:(iv) any set of n jordan regions with near linear union complexity admits a conflict-free (cf) coloring with polylogarithmic number of colors.(v) any set of n axis-parallel rectangles admits a cf-coloring with o(log2(n)) colors.
theory of semidefinite programming for sensor network localization. we analyze the semidefinite programming (sdp) based model and method for the position estimation problem in sensor network localization and other euclidean distance geometry applications. we use sdp duality and interior-point algorithm theories to prove that the sdp localizes any network or graph that has unique sensor positions to fit given distance measures. therefore, we show, for the first time, that these networks can be localized in polynomial time. we also give a simple and efficient criterion for checking whether a given instance of the localization problem has a unique realization in $$\mathcal{r}^2$$ using graph rigidity theory. finally, we introduce a notion called strong localizability and show that the sdp model will identify all strongly localizable sub-networks in the input network.
multicommodity facility location. multicommodity facility location refers to the extension of facility location to allow for different clients having demand for different goods, from among a finite set of goods. this leads to several optimization problems, depending on the costs of opening facilities (now a function of the commodities it serves). in this paper, we introduce and study some variants of multicommodity facility location, and provide approximation algorithms and hardness results for them.
a semidefinite programming approach to tensegrity theory and realizability of graphs. recently, connelly and sloughter [14] have introduced the notion of d-realizability of graphs and have, among other things, given a complete characterization of the class of 3-realizable graphs. however, their work has left open the question of finding an algorithm for realizing those graphs. in this paper, we resolve that question by showing that the semidefinite programming (sdp) approach of [11, 32] can be used for realizing 3-realizable graphs. specifically, we use sdp duality theory to show that given a graph g and a set of lengths on its edges, the optimal dual multipliers of a certain sdp give rise to a proper equilibrium stress for some realization of g. using this result and the techniques in [14, 31], we then obtain a polynomial time algorithm for (approximately) realizing 3-realizable graphs. our results also establish a little-explored connection between sdp and tensegrity theories and allow us to derive some interesting properties of tensegrity frameworks.
spanning trees short or small. we study the problem of finding small trees. classical network design problems are considered with the additional constraint that only a specified number $k$ of nodes are required to be connected in the solution. a prototypical example is the $k$mst problem in which we require a tree of minimum weight spanning at least $k$ nodes in an edge-weighted graph. we show that the $k$mst problem is np-hard even for points in the euclidean plane. we provide approximation algorithms with performance ratio $2\sqrt{k}$ for the general edge-weighted case and $o(k^{1/4})$ for the case of points in the plane. polynomial-time exact solutions are also presented for the class of treewidth-bounded graphs, which includes trees, series-parallel graphs, and bounded bandwidth graphs, and for points on the boundary of a convex region in the euclidean plane. we also investigate the problem of finding short trees and, more generally, that of finding networks with minimum diameter. a simple technique is used to provide a polynomial-time solution for finding $k$-trees of minimum diameter. we identify easy and hard problems arising in finding short networks using a framework due to t. c. hu.