waashk/dblp huggingface dataset:
on translating a set of rectangles given a collection of disjoint objects in the plane, we are interested in translating them by a common vector. if we have a primitive for translating one object at a time, then the order in which the objects can individually be translated is often geometrically constrained. in this paper we study the nature of these constraints and exhibit optimal algorithms for finding valid motion ordering for several different classes of objects. these algorithms find use in computer display applications.
provisioning a virtual private network: a network design problem for multicommodity flow. consider a setting in which a group of nodes, situated in a large underlying network, wishes to reserve bandwidth on which to support communication. virtual private networks (vpns) are services that support such a construct; rather than building a new physical network on the group of nodes that must be connected, bandwidth in the underlying network is reserved for communication within the group, forming a virtual &ldquo;sub-network.&rdquo;provisioning a virtual private network over a set off terminals gives rise to the following general network design problem. we have bounds on the cumulative amount of traffic each terminal can send and receive; we must choose a path for each pair of terminals, and a bandwidth allocation for each edge of the network, so that any traffic matrix consistent with the given upper bounds can be feasibly routed. thus, we are seeking to design a network that can support a continuum of possible traffic scenarios.we provide optimal and approximate algorithms for several variants of this problem, depending on whether the traffic matrix is required to be symmetric, and on whether the designed network is required to be a tree (a natural constraint in a number of basic applications). we also establish a relation between this collection of network design problems and a variant of the facility location problem introduced by karger and minkoff; we extend their results by providing a stronger approximation algorithm for this latter problem.
simpler and better approximation algorithms for network design. we give simple and easy-to-analyze randomized approximation algorithms for several well-studied np-hard network design problems. our algorithms improve over the previously best known approximation ratios. our main results are the following.we give a randomized 3.55-approximation algorithm for the connected facility location problem. the algorithm requires three lines to state, one page to analyze, and improves the best-known performance guarantee for the problem.we give a 5.55-approximation algorithm for virtual private network design. previously, constant-factor approximation algorithms were known only for special cases of this problem.we give a simple constant-factor approximation algorithm for the single-sink buy-at-bulk network design problem. our performance guarantee improves over what was previously known, and is an order of magnitude improvement over previous combinatorial approximation algorithms for the problem.
boosted sampling: approximation algorithms for stochastic optimization. several combinatorial optimization problems choose elements to minimize the total cost of constructing a feasible solution that satisfies requirements of clients. in the steiner tree problem, for example, edges must be chosen to connect terminals (clients); in vertex cover, vertices must be chosen to cover edges (clients); in facility location, facilities must be chosen and demand vertices (clients) connected to these chosen facilities. we consider a stochastic version of such a problem where the solution is constructed in two stages: before the actual requirements materialize, we can choose elements in a first stage. the actual requirements are then revealed, drawn from a pre-specified probability distribution π thereupon, some more elements may be chosen to obtain a feasible solution for the actual requirements. however, in this second (recourse) stage, choosing an element is costlier by a factor of σ> 1. the goal is to minimize the first stage cost plus the expected second stage cost.we give a general yet simple technique to adapt approximation algorithms for several deterministic problems to their stochastic versions via the following method. first stage: draw σ independent sets of clients from the distribution π and apply the approximation algorithm to construct a feasible solution for the union of these sets. second stage: since the actual requirements have now been revealed, augment the first-stage solution to be feasible for these requirements. we use this framework to derive constant factor approximations for stochastic versions of vertex cover, steiner tree and uncapacitated facility location for arbitrary distributions π in one fell swoop. for special (product) distributions, we obtain additional and improved results. our techniques adapt and use the notion of strict cost-shares introduced in [5].
an np-complete number-theoretic problem systems of nonlinear equations of the form d: a&ymarc; &equil; &sgr;marc;.(x), where a is an m&times;n matrix of rational constants and &ymarc; &equil; (y1,...,yn), &sgr;(x) &equil; (&sgr;1(x),..., &sgr;m (x)) are column vectors are considered. each &sgr;i(x) is of the form ri(x) or @@@@ri(x)@@@@, where ri(x) is a rational function of x with rational coefficients. it is shown that the problem of determining for a given system d whether there exists a nonnegative integral solution (y1,...,yn,x) satisfying d is decidable. in fact, the problem is np-complete when restricted to systems d in which the maximum degree of the polynomials defining the &sgr;i(x)'s is bounded by some fixed polynomial in the length of the representation of d. some recent results connecting diophantine equations and counter machines are briefly mentioned.
the complexity of the equivalence problem for counter machines, semilinear sets, and simple programs it is shown that the class of relations (functions) definable by presburger formulas is exactly the class of relations (functions) computable by finite-reversal multicounter machines. an upper bound of 2c(n/logn)4 on the deterministic time complexity of the equivalence problem for such machines is established. in fact, it is proved that the inequivalence problem is np-complete. these results are used to derive some upper bounds on the complexity of the equivalence problem for semilinear sets and simple programs. for example, it is shown that the equivalence problem for semilinear sets (these sets are exactly the presburger relations) is decidable in deterministic time 22cn2. a class of programs which realize exactly the relations (functions) definable by presburger formulas is shown to have an np-complete inequivalence problem. hence, its equivalence problem is decidable in deterministic time 2p(n). this bound is a four-level exponential improvement over a previously known result.
trees, automata, and games in 1969 rabin introduced tree automata and proved one of the deepest decidability results. if you worked on decision problems you did most probably use rabin's result. but did you make your way through rabin's cumbersome proof with its induction on countable ordinals? building on ideas of our predecessors-&-mdash;and especially those of b-&-uuml;chi-&-mdash;we give here an alternative and transparent proof of rabin's result. generalizations and further results will be published elsewhere.
limits to list decodability of linear codes. we consider the problem of the best possible relation between the list decodability of a binary linear code and its minimum distance. we prove, under a widely-believed number-theoretic conjecture, that the classical "johnson bound" gives, in general, the best possible relation between the list decoding radius of a code and its minimum distance. the analogous result is known to hold by a folklore random coding argument for the case of non-linear codes, but the linear case is more subtle and has remained open.we prove our result by exhibiting an infinite family of binary linear codes of "large" minimum distance with a super-polynomial number (in blocklength) of codewords all within a hamming ball of radius close to the johnson bound. even the existence of codes with a super-polynomial number of codewords in a ball of radius bounded away from the minimum distance (let alone radius close to the johnson bound) was open prior to our work. we also unconditionally prove the "tightness" of the johnson bound for decoding with list size that is an arbitrarily large constant.
better extractors for better codes? we present an explicit construction of codes that can be list decoded from a fraction (1-ε) of errors in sub-exponential time and which have rate ε/logo(1)(1/ε). this comes close to the optimal rate of ω(ε), and is the first sub-exponential complexity construction to beat the rate of ε2 achieved by reed-solomon or algebraic-geometric codes. our construction is based on recent extractor constructions with very good seed length [17]. while the "standard" way of viewing extractors as codes (as in [16]) cannot beat the o(ε2) rate barrier due to the 2 log (1/ε) lower bound on seed length for extractors, we use such extractor codes as a component in a well-known expander-based construction scheme to get our result. the o(ε2) rate barrier also arises if one argues about list decoding using the minimum distance (via the so-called johnson bound) --- so this also gives the first explicit construction that "beats the johnson bound" for list decoding from errors.the main message from our work is perhaps conceptual, namely that good strong extractors for low min-entropies will yield near-optimal list decodable codes. given all the progress that has been made on extractors, we view this as an optimistic avenue to look for better list decodable codes, both by looking for better explicit extractor constructions, as well as by importing non-trivial techniques from the extractor world in reasoning about and constructing codes.
near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets. we present an explicit construction of linear-time encodable and decodable codes of rate r which can correct a fraction (1&mdash:r&egr;)/2 of errors over an alphabet of constant size depending only on &egr;, for every 0 < r < 1 and arbitrarily small &egr;> 0. the error-correction performance of these codes is optimal as seen by the singleton bound (these are "near-mds" codes). such near-mds linear-time codes were known for the decoding from erasures [2]; our construction generalizes this to handle errors as well. concatenating these codes with good, constant-sized binary codes gives a construction of linear-time binary codes which meet the so-called "zyablov bound". in a nutshell, our results match the performance of the previously known explicit constructions of codes that had polynomial time encoding and decoding, but in addition have linear time encoding and decoding algorithms.we also obtain some results for list decoding targeted at the situation when the fraction of errors is very large, namely (1&mdash;&egr;) for an arbitrarily small constant &egr; > 0. the previously known constructions of such codes of good rate over constant-sized alphabets either used algebraic-geometric codes and thus suffered from complicated constructions and slow decoding, or as in the recent work of the authors [9], had fast encoding/decoding, but suffered from an alphabet size that was exponential in 1/&egr;. we present two constructions of such codes with rate close to &ohgr;(&egr;2) over an alphabet of size quasi-polynomial in 1/&egr;. one of the constructions, at the expense of a slight worsening of the rate, can achieve an alphabet size which is polynomial in 1/&egr;. it also yields constructions of codes for list decoding from erasures which achieve new trade-offs. in particular, we construct codes of rate close to the optimal &ohgr;(&egr;) rate which can be efficiently list decoded from a fraction (1&mdash;&egr;) of erasures.
linear time encodable and list decodable codes. we present the first construction of error-correcting codes which can be (list) decoded from a noise fraction arbitrarily close to 1 in linear time. specifically, we present an explicit construction of codes which can be encoded in linear time as well as list decoded in linear time from a fraction (1-ε) of errors for arbitrary ε > 0. the rate and alphabet size of the construction are constants that depend only on ε. our construction involves devising a new combinatorial approach to list decoding, in contrast to all previous approaches which relied on the power of decoding algorithms for algebraic codes like reed-solomon codes.our result implies that it is possible to have, and in fact explicitly specifies, a coding scheme for arbitrarily large noise thresholds with only constant redundancy in the encoding and constant amount of work (at both the sending and receiving ends) for each bit of information to be communicated. such a result was known for certain probabilistic error models, and here we show that this is possible under the stronger adversarial noise model as well.
near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. we study the approximability of edge-disjoint paths and related problems. in the edge-disjoint paths (edp) problem, we are given a network g with source-sink pairs (si, ti), 1 ≤i≤k, and the goal is to find a largest subset of source-sink pairs that can be simultaneously connected in an edge-disjoint manner. we show that in directed networks, for any ε>0, edp is np-hard to approximate within m1/2-ε. we also design simple approximation algorithms that achieve essentially matching approximation guarantees for some generalizations of edp. another related class of routing problems that we study concerns edp with the additional constraint that the routing paths be of bounded length. we show that, for any ε > 0, bounded length edp is hard to approximate within m1/2-ε even in undirected networks, and give an o(√m)-approximation algorithm for it. for directed networks, we show that even the single source-sink pair case (i.e. find the maximum number of paths of bounded length between a given source-sink pair) is hard to approximate within m1/2-ε, for any ε > 0.
limits to list decoding reed-solomon codes. in this paper, we prove the following two results that expose some combinatorial limitations to list decoding reed-solomon codes.given n distinct elements α1,...,αn from a field f, and n subsets s1,...,sn of f each of size at most l, the list decoding algorithm of guruswami and sudan [7] can in polynomial time output all polynomials p of degree at most k which satisfy p(αi) ∈ si for every i, as long as l < ⌈ n/k ⌉. we show that the performance of this algorithm is the best possible in a strong sense; specifically, we show that when l = ⌈ n/k ⌉, the list of output polynomials can be super-polynomially large in n. one way to interpret our result is the following. the algorithm in [7] can, when given as input $n'$ distinct pairs (βi,∈i) ∈ f2 (the βi's need not be distinct), find and output all degree k polynomials p such that p(βi) = γi for at least $t$ values of i, provided t > √k n'. by our result, an improvement to the reed-solomon list decoder of [7] that works with slightly smaller agreement, say t > √kn' - k/2, can only be obtained by exploiting some property of the βi's (for example, their (near) distinctness).for reed-solomon codes of block length $n$ and dimension k where k = nδ for small enough δ, we exhibit an explicit received word r with a super-polynomial number of reed-solomon codewords that agree with it on $(2 - ε) k locations, for any desired ε > 0 (we note agreement of k is trivial to achieve). such a bound was known earlier only for a non-explicit center. we remark that finding explicit bad list decoding configurations is of significant interest --- for example the best known rate vs. distance trade-off is based on a bad list decoding configuration for algebraic-geometric codes [14] which is unfortunately not explicitly known.
explicit capacity-achieving list-decodable codes. for every 0 < r < 1 and ε > 0, we present an explicit construction of error-correcting codes of rate r that can be list decoded in polynomial time up to a fraction (1-r-ε) of errors. these codes achieve the "capacity" for decoding from adversarial errors, i.e., achieve the optimal trade-off between rate and error-correction radius. at least theoretically, this meets one of the central challenges in coding theory.prior to this work, explicit codes achieving capacity were not known for any rate r. in fact, our codes are the first to beat the error-correction radius of 1-√r, that was achieved for reed-solomon (rs) codes in [9], for all rates r. (for rates r < 1/16, parvaresh and vardy [12] had recently improved upon the 1-√r bound; for r → 0, their algorithm can decode a fraction 1-o(r log(1/r)) of errors.)our codes are simple to describe --- they are certain folded reed-solomon codes, which are in fact exactly rs codes, but viewed as a code over a larger alphabet by careful bundling of codeword symbols. given the ubiquity of rs codes, this is an appealing feature of our result, since the codes we propose are not too far from the ones in actual use.the main insight in our work is that some carefully chosen folded rs codes are "compressed" versions of a related family of parvaresh-vardy codes. further, the decoding of the folded rs codes can be reduced to list decoding the related parvaresh-vardy codes. the alphabet size of these folded rs codes is polynomial in the block length. this can be reduced to a constant that depends on the distance ε to capacity using ideas concerning "list recovering" and expander-based codes from [7, 8]. concatenating the folded rs codes with suitable inner codes also gives us polytime constructible binary codes that can be efficiently list decoded up to the zyablov bound.
classical deterministic complexity of edmonds' problem and quantum entanglement. generalizing a decision problem for bipartite perfect matching, j. edmonds introduced in [14] the problem (now known as the edmonds problem) of deciding if a given linear subspace of m(n) contains a nonsingular matrix, where m(n) stands for the linear space of complex nxn matrices. this problem led to many fundamental developments in matroid theory etc.classical matching theory can be defined in terms of matrices with nonnegative entries. the notion of positive operator, central in quantum theory, is a natural generalization of matrices with nonnegative entries. (here operator refers to maps from matrices to matrices.) first, we reformulate the edmonds problem in terms of of completely positive operators, or equivalently, in terms of bipartite density matrices. it turns out that one of the most important cases when edmonds' problem can be solved in polynomial deterministic time, i.e. an intersection of two geometric matroids, corresponds to unentangled (aka separable) bipartite density matrices. we introduce a very general class (or promise) of linear subspaces of m(n) on which there exists a polynomial deterministic time algorithm to solve edmonds' problem. the algorithm is a thoroughgoing generalization of algorithms in [23], [26], and its analysis benefits from an operator analog of permanents, so called quantum permanents. finally, we prove that the weak membership problem for the convex set of separable normalized bipartite density matrices is np-hard.
hyperbolic polynomials approach to van der waerden/schrijver-valiant like conjectures: sharper bounds, simpler proofs and algorithmic applications. let p(x1,...,xn) = p(x) , x ∈ rn be a homogeneous polynomial of degree n in n real variables, e = (1,1,..,1) ∈ rn be a vector of all ones . such a polynomial p is called e-hyperbolic if for all real vectors x ∈ rn the univariate polynomial equation p(te - x) = 0 has all real roots λ1(x) ≥ ... ≥ λn(x). the number of nonzero roots |i :λi(x) ≠ 0 | is called rankp(x). an e-hyperbolic polynomial p is called pos-hyperbolic if roots of vectors x ∈ rn+ with nonnegative coordinates are also nonnegative (the orthant rn+ belongs to the hyperbolic cone) and p(e) > 0. below e1,...,en stands for the canonical orthogonal basis in rn. the main results of this paper states that if p(x1,x2,...,xn) is a pos-hyperbolic (homogeneous) polynomial of degree n, rankp (ei) = ri and p(x1,x2,...,xn) ≥ ∏1 ≤ i ≤ n xi ; xi > 0, 1 ≤ i ≤ n, then the following inequality holds ∂n/∂ x1...∂ xn p(0,...,0) ≥ ∏1 ≤ i ≤ n (gi-1/gi)gi-1, where gi = min(ri , n+1-i) . this inequality is a vast (and unifying) generalization of the van der waerden conjecture on the permanents of doubly stochastic matrices as well as the schrijver-valiant conjecture on the number of perfect matchings in k-regular bipartite graphs. these two famous results correspond to the pos-hyperbolic polynomials which are products of linear forms with nonnegative coefficients.our proof is relatively simple and "noncomputational"; it actually slightly improves schrijver's lower bound, and uses very basic (more or less centered around rolle's theorem) properties of hyperbolic polynomials. we present some important algorithmic applications of the result, including a polynomial time deterministic algorithm approximating the permanent of n x n entry-wise non-negative matrices within a multiplicative factor en/nm for any fixed positive m; and a deterministic poly-time algorithm approximating the permanent of n x n matrix a having at most k nonzero entries in each column to within a multiplicative factor (k-1/k)(k-1)n.this paper introduces a new powerful "polynomial" technique , which allows us to simplify and unify hard and key known results as well as to prove new important theorems and get new algorithms.
oblivious routing in directed graphs with random demands. oblivious routing algorithms for general undirected networks were introduced by räcke, and this work has led to many subsequent improvements and applications. more precisely, räcke showed that there is an oblivious routing algorithm with polylogarithmic competitive ratio (w.r.t. edge congestion) for any undirected graph. comparatively little positive results are known about oblivious routing in general directed networks. using a novel approach, we present the first oblivious routing algorithm which is o(log2 n) competitive with high probability in directed graphs given that the demands are chosen randomly from a known demand-distribution. on the other hand, we show that no oblivious routing algorithm can be o(logn/log log n) competitive even with constant probability in general directed graphs.our routing algorithms are not oblivious in the traditional definition, but we add the concept of demand-dependence, i.e., the path chosen for an s-t pair may depend on the demand between s and t. this concept that still preserves that routing decisions are only based on local information proves very powerful in our randomized demand model.finally, we show that our approach for designing competitive oblivious routing algorithms is quite general and has applications in other contexts like stochastic scheduling.
on the communication complexity of graph properties we prove &thgr;(n log n) bounds for the deterministic 2-way communication complexity of the graph properties connectivity, s-t-connectivity and bipartiteness (for arbitrary partitions of the variables into two sets of equal size). the proofs are based on combinatorial results of dowling-wilson and lov&aacute;sz-saks about partition matrices using the m&ouml;bius function, and the regularity lemma of szemer&eacute;di. the bounds imply improved lower bounds for the vlsi complexity of these decision problems and sharp bounds for a generalized decision tree model which is related to the notion of evasiveness.