waashk/dblp huggingface dataset:
intersecting is easier than sorting this paper settles a long-standing open question of computational geometry: is it possible to compute all k intersections between n arbitrary line segments in time linear in k? we answer this question affirmatively by presenting the first algorithm with a running time of the form o(k + f(n)), where f is a subquadratic function of n. the function f we achieve is actually quasi-linear in n, which makes our algorithm the most efficient to date for each value of k. to obtain this result we must turn away from traditional, sweep-line-based schemes. instead, we introduce a new hierarchical strategy for dealing with segments without ever reducing the dimensionality of the problem. this framework is used to solve other related problems. in particular, we are able to present the first subquadratic algorithm for counting intersections (as opposed to reporting each of them explicitly), and we give the first optimal algorithm for computing the intersections of a line arrangement with a query segment. using duality arguments we also present an improved algorithm for a point enclosure problem.
decomposing a polygon into its convex parts a common operation in geometric computing is the decomposition of complex structures into more basic structures. since it is easier to apply most algorithms to triangles or arbitrary convex polygons, there is considerable interest in finding fast algorithms for such decompositions. we consider the problem of decomposing a simple (non-convex) polygon into the union of a minimal number of convex polygons. although the structure of the problem led to the conjecture that it was np-complete, we have been able to reach polynomial time bounded algorithms for exact solution as well as low degree polynomial time bounded algorithm/or approximation methods.
detection is easier than computation (extended abstract) perhaps the most important application of computer geometry involves determining whether a pair of convex objects intersect. this problem is well understood in a model of computation where the objects are given as input and their intersection is returned as output. however, for many applications, we may assume that the objects already exist within the computer and that the only output desired is a single piece of data giving a common point if the objects intersect or reporting no intersection if they are disjoint. for this problem, none of the previous lower bounds are valid and we propose algorithms requiring sublinear time for their solution in 2 and 3 dimensions.
the complexity of cutting convex polytopes throughout this paper, we use the term subdivision as a shorthand for &ldquo;a subdivision of e2 into convex regions&rdquo;. a subdivision is said to be of size n if it is made of n convex (open) regions, and it is of degree d if every region is adjacent to at most d other regions. we define the line span of a subdivision as the maximum number of regions which can be intersected by a single line (section 3).
lines in space-combinatorics, algorithms and applications we study combinatorial and algorithmic problems involving arrangements of n lines in 3-dimensional space, and then present applications of our results to a variety of problems on polyhedral terrains. our main results include: a tight &thgr;(n2) bound on the complexity of the space of all lines passing above all the n given lines (their &ldquo;upper envelope&rdquo;) and satisfying a certain orientation consistency constraint. a preprocessing procedure using near-quadratic time and storage that builds a structure supporting &ogr;(log n) time queries for testing if a line lies above all the given lines. an &ogr;(n4/3+&egr;) randomized expected time algorithm, for any fixed &egr; > 0, that tests the &ldquo;towering property&rdquo;: do n given red lines lie all above n given blue lines? a preprocessing procedure for a polyhedral terrain &sgr; with n edges, that uses near-quadratic time and storage and builds a structure supporting &ogr;(log2 n) time rayshooting queries for computing the first intersection of an arbitrary query ray with &sgr;. finding the smallest vertical distance between two disjoint polyhedral terrains with a total of n edges, in time &ogr;(n4/3+&egr;), for any &egr; > 0. computing the upper envelope (pointwise maximum) of two polyhedral terrains with a total of n edges, in time &ogr;(n1.5+&egr; + klog2 n), for any &egr; > 0, where &kgr; is the size of the output envelope. the tools used to obtain these results include pl&uuml;cker coordinates for lines in space, random sampling in geometric problems, and a new variant of segment trees.
lower bounds for intersection searching and fractional cascading in higher dimension. given an n-edge convex subdivision of the plane, is it possible to report its k intersections with a query line segment in o(k + polylog(n)) time, using subquadratic storage? if the query is a plane and the input is a polytope with n vertices, can one achieve o(k + polylog(n)) time with subcubic storage? does any convex polytope have a boundary dominant dobkin-kirkpatrick hierarchy? can fractional cascading be generalized to planar maps instead of linear lists? we prove that the answer to all of these questions is no, and we derive near-optimal solutions to these classical problems.
sublinear geometric algorithms. we initiate an investigation of sublinear algorithms for geometric problems in two and three dimensions. we give optimal algorithms for intersection detection of convex polygons and polyhedra, point location in two-dimensional delaunay triangulations and voronoi diagrams, and ray shooting in convex polyhedra, all of which run in time o(√n), where n is the size of the input. we also provide sublinear solutions for the approximate evaluation of the volume of a convex polytope and the length of the shortest path between two points on the boundary.
a model of computation for vlsi with related complexity results a new model of computation for vlsi, based on the assumption that time for propagating information is at least linear in the distance, is proposed. while accommodating for basic laws of physics, the model is designed to be general and technology independent. thus, from a complexity viewpoint, it is especially suited for deriving lower bounds and trade-offs. new results for a number of problems, including fan-in, transitive functions, matrix multiplication, and sorting are presented. as regards upper bounds, it must be noted that, because of communication costs, the model clearly favors regular and pipelined architectures (e.g., systolic arrays).
approximation schemes for preemptive weighted flow time. (math) we present the first approximation schemes for minimizing weighted flow time on a single machine with preemption. our first result is an algorithm that computes a (1+&egr;)-approximate solution for any instance of weighted flow time in o(no(ln w ln p/&egr;3)) time; here p is the ratio of maximum job processing time to minimum job processing time, and w is the ratio of maximum job weight to minimum job weight. this result directly gives a quasi-ptas for weighted flow time when p and w are poly-bounded, and a ptas when they are both o(1). we strengthen the former result to show that in order to get a quasi- ptas it suffices to have just one of p and w to be poly-bounded. our result provides strong evidence to the hypothesis that the weighted flow time problem has a ptas. we note that the problem is strongly np-hard even when p and w are o(1). we next consider two important special cases of weighted flow time, namely, when p is o(1) and w is arbitrary, and when the weight of a job is inverse of its processing time referred to as the stretch metric. for both of the above special cases we obtain a (1+&egr;)-approximation for any &egr; &rho; 0 by using a randomized partitioning scheme to reduce an arbitrary instance to several instances all of which have p and w bounded by a constant that depends only on &egr;.
the all-or-nothing multicommodity flow problem. we consider the all-or-nothing multicommodity flow problem in general graphs. we are given a capacitated undirected graph g=(v,e,u) and set of k pairs s1 t1, s2t2, …, sktk. each pair has a unit demand. the objective is to find a largest subset s of 1,2,…,k such that for every i in s we can send a flow of one unit between si and ti. note that this differs from the edge-disjoint path problem (edp) in that we do not insist on integral flows for the pairs. this problem is np-hard, and apx-hard, even on trees. for trees, a 2--approximation is known for the cardinality case and a 4--approximation for the weighted case. in this paper we build on a recent result of räcke on low congestion oblivious routing in undirected graphs to obtain a poly-logarithmic approximation for the all-or-nothing problem in general undirected graphs. the best previous known approximation for all-or-nothing flow problem was o(min(n<2/3, √m)), the same as that for edp. our algorithm extends to the case where each pair siti has a demand di associated with it and we need to completely route di to get credit for pair i. we also consider the online admission control version where pairs arrive online and the algorithm has to decide immediately on its arrival whether to accept it or not. we obtain a randomized algorithm with a competitive ratio that is similar to the approximation ratio for the offline algorithm.
multicommodity flow, well-linked terminals, and routing problems. we study multicommodity routing problems in both edge and node capacitated undirected graphs. the input to each problem is a capacitated graph g=(v,e) and a set τ of node pairs. in the simplest setting, the goal is to route a unit of flow for as many pairs as possible subject to the edge (node) capacity constraints. if the flow for a routed pair is required to be along a single path, it is the well-studied disjoint paths problem. if we allow fractional routings of the flow, it is known as the all-or-nothing flow problem. the nodes in τ are referred to as terminals.in recent work [8,9], the authors obtained the first poly-logarithmic approximation algorithms for some edge routing problems. a key idea in these algorithms is to decompose an instance into a collection of instances in which the terminals are well-linked. informally speaking, a set of nodes is well-linked in a graph if it does not have small separators. a decomposition into well-linked instances was previously achieved in [8] via räcke's hierarchical graph decomposition for oblivious routing [32]. in this paper, we design a simple new decomposition algorithm that is based on computing sparse cuts in a graph. our new algorithm improves the earlier results for edge routing problems. another important advantage of the algorithm is that it also applies to node-capacitated problems. we note that for oblivious routing with node capacities, an ω√n) lower bound is known on the congestion [18], and hence the oblivious routing approach cannot yield poly-logarithmic bounds for well-linked decompositions. using the new decomposition, we obtain a poly-logarithmic approximation for the node capacitated all-or-nothing flow problem in general graphs and node-disjoint path problem in planar graphs with o(1) congestion. we also show that the flow-cut gap for product multicommodity flows in node capacitated planar graphs is o(1), improving upon the o(log n) bound from [28].
edge-disjoint paths in planar graphs with constant congestion. we study the maximum edge-disjoint paths problem in undirected planar graphs: given a graph $g$ and node pairs (demands) $s_1t_1$, $s_2t_2$, $\dots$, $s_kt_k$, the goal is to maximize the number of demands that can be connected (routed) by edge-disjoint paths. the natural multicommodity flow relaxation has an $\omega(\sqrt{n})$ integrality gap, where $n$ is the number of nodes in $g$. motivated by this, we consider solutions with small constant congestion $c>1$, that is, solutions in which up to $c$ paths are allowed to use an edge (alternatively, each edge has a capacity of $c$). in previous work we obtained an $o(\log n)$ approximation with congestion 2 via the flow relaxation. this was based on a method of decomposing into well-linked subproblems. in this paper we obtain an $o(1)$ approximation with congestion 4. to obtain this improvement we develop an alternative decomposition that is specific to planar graphs. the decomposition produces instances that we call okamura-seymour (os) instances. these have the property that all terminals lie on a single face. another ingredient we develop is a constant factor approximation for the all-or-nothing flow problem on os instances via the flow relaxation.
algorithms for minimizing weighted flow time. we study the problem of minimizing weighted flow time on a single machine in the preemptive setting. we present an o(\log^2 p)-competitive semi-online algorithm where p is the ratio of the maximum and minimum processing times of jobs in the system. in the offline setting we show that a (2+\eps)-approximation is achievable in quasi-polynomial time. these are the first non-trivial results for the weighted versions of minimizing flow time. for multiple machines we show that no competitive randomized online algorithm exists for weighted flow time. we also present an improved online algorithm for minimizing total stretch (a special case of weighted flow time) on multiple machines.
on algorithms for discrete and approximate brouwer fixed points. we study the algorithmic complexity of the discrete fixed point problem and develop an asymptotic matching bound for a cube in any constantly bounded finite dimension. to obtain our upper bound, we derive a new fixed point theorem, based on a novel characterization of boundary conditions for the existence of fixed points.in addition, exploring a linkage with the approximation problem of the continuous fixed point problem, we obtain asymptotic matching bounds for complexity of the approximate brouwer fixed point problem in the continuous case for lipschitz functions that close a previous exponential gap. it settles a fifteen years old open problem of hirsch, papadimitriou and vavasis by improving both the upper and lower bounds.our new characterization for existence of a fixed point is also applicable to functions defined on non-convex domain and makes it a potentially useful tool for design and analysis of algorithms for fixed points in general domain.
linear fpt reductions and computational lower bounds. we develop new techniques for deriving very strong computational lower bounds for a class of well-known np-hard problems, including weighted satisfiability, dominating set, hitting set, set cover, clique, and independent set. for example, although a trivial enumeration can easily test in time o(nk) if a given graph of n vertices has a clique of size k, we prove that unless an unlikely collapse occurs in parameterized complexity theory, the problem is not solvable in time f(k) no(k) for any function f, even if we restrict the parameter value k to be bounded by an arbitrarily small function of n. under the same assumption, we prove that even if we restrict the parameter values k to be θ(μ(n)) for any reasonable function μ, no algorithm of running time no(k) can test if a graph of n vertices has a clique of size k. similar strong lower bounds are also derived for other problems in the above class. our techniques can be extended to derive computational lower bounds on approximation algorithms for np-hard optimization problems. for example, we prove that the np-hard distinguishing substring selection problem, for which a polynomial time approximation scheme has been recently developed, has no polynomial time approximation schemes of running time f(1/ε)no(1/ε) for any function f unless an unlikely collapse occurs in parameterized complexity theory.
reducing randomness via irrational numbers. we propose a general methodology for testing whether a given polynomial with integer coefficients is identically zero. the methodology evaluates the polynomial at efficiently computable approximations of suitable irrational points. in contrast to the classical technique of demillo, lipton, schwartz, and zippel, this methodology can decrease the error probability by increasing the precision of the approximations instead of using more random bits. consequently, randomized algorithms that use the classical technique can generally be improved using the new methodology. to demonstrate the methodology, we discuss two nontrivial applications. the first is to decide whether a graph has a perfect matching in parallel. our new nc algorithm uses fewer random bits while doing less work than the previously best nc algorithm by chari, rohatgi, and srinivasan. the second application is to test the equality of two multisets of integers. our new algorithm improves upon the previously best algorithms by blum and kannan and can speed up their checking algorithm for sorting programs on a large range of inputs.
(almost) tight bounds and existence theorems for confluent flows. a flow is said to be confluent if at any node all the flow leaves along a single edge. given a directed graph g with k sinks and non-negative demands on all the nodes of g, we consider the problem of determining a confluent flow that routes every node demand to some sink such that the maximum congestion at a sink is minimized. confluent flows arise in a variety of application areas, most notably in networking; in fact, most flows in the internet are confluent since internet routing is destination based.we present near-tight approximation algorithms, hardness results, and existence theorems for confluent flows. the main result of this paper is a polynomial-time algorithm for determining a confluent flow with congestion at most 1 + ln(k) in g, if g admits a splittable flow with congestion at most 1. we complement this result in two directions. first, we present a graph g that admits a splittable flow with congestion at most 1, yet no confluent flow with congestion smaller than hk, thus establishing tight upper and lower bounds to within an additive constant less than 1. second, we show that it is np-hard to approximate the congestion of an optimal confluent flow to within a factor of (lg k)/2, thus resolving the polynomial-time approximability to within a multiplicative constant. we also consider a demand maximization version of the problem. we show that if g admits a splittable flow of congestion at most 1, then a variant of the congestion minimization algorithm yields a confluent flow in g with congestion at most 1 that satisfies 1/3 fraction of total demand.we show that the gap between confluent flows and splittable flows is much smaller, if the underlying graph were k connected. in particular, we prove that k-connected graphs with k sinks admit confluent flows of congestion less than c + dmax, where c is the congestion of the best splittable flow, and dmax is the maximum demand of any node in g. the proof of this existence theorem is non-constructive and relies on topological techniques introduced in [16].
optimal buy-and-hold strategies for financial markets with bounded daily returns. in the context of investment analysis, we formulate an abstract online computing problem called a planning game and develop general tools for solving such a game. we then use the tools to investigate a practical buy-and-hold trading problem faced by long-term investors in stocks. we obtain the unique optimal static online algorithm for the problem and determine its exact competitive ratio. we also compare this algorithm with the popular dollar averaging strategy using actual market data.
meet and merge: approximation algorithms for confluent flows. in this paper, we investigate the problem of determining confluent flows with minimum congestion. a flow of a given commodity is said to be confluent if at any node all the flow of the commodity departs along a single edge. confluent flows appear in a variety of application areas ranging from wireless communications to evacuations; in fact, most flows in the internet are confluent since internet routing is destination based. we consider the single-commodity confluent flow problem, in which we are given an n-node directed network g, a sink t and supplies at each node, and the goal is to find a confluent flow that routes all the supplies to the sink while minimizing the maximum edge congestion. our main result is an approximation algorithm, based on randomized rounding, for the special case when all the supplies are uniform; the algorithm finds a confluent flow with edge (and node) congestion o(c^2log^3n), where c is the node congestion of a splittable flow with minimum node congestion; here the node congestion of a flow is the maximum, over all nodes other than t, of the congestion at a node. this implies an o@?(n) approximation algorithm for the problem with uniform supplies. our result relies on the analysis of a natural probabilistic process defined on directed acyclic graphs, that may be of independent interest. for tree networks, we present an optimal polynomial-time algorithm for a multi-sink generalization of the above confluent flow problem. we show that it is np-hard to approximate the congestion of the optimal confluent flow for general networks to within a factor of 32. we also establish a lower bound on the gap between confluent and splittable flows, and consider multi-commodity and fractional versions of confluent flow problems.
approximation algorithms for network design with metric costs. we study undirected networks with edge costs that satisfy the triangle inequality. let $n$ denote the number of nodes. we present an $o(1)$-approximation algorithm for a generalization of the metric-cost subset $k$-node-connectivity problem. our approximation guarantee is proved via lower bounds that apply to the simple edge-connectivity version of the problem, where the requirements are for edge-disjoint paths rather than for openly node-disjoint paths. a corollary is that, for metric costs and for each $k=1,2,\dots,n-1$, there exists a $k$-node connected graph whose cost is within a factor of ${ 22\/}$ of the cost of any simple $k$-edge connected graph. based on our $o(1)$-approximation algorithm, we present an $o(\log r_{\max})$-approximation algorithm for the metric-cost node-connectivity survivable network design problem, where $r_{\max}$ denotes the maximum requirement over all pairs of nodes. our results contrast with the case of edge costs of 0 or 1, where kortsarz, krauthgamer, and lee. [siam j. comput., 33 (2004), pp. 704-720] recently proved, assuming np$\nsubseteq\;$dtime($n^{polylog(n)}$), a hardness-of-approximation lower bound of $2^{\log^{1-\epsilon}n}$ for the subset $k$-node-connectivity problem, where $\epsilon$ denotes a small positive number.
approximation algorithms for minimum-cost k-vertex connected subgraphs. (math) we present two new algorithms for the problem of finding a minimum-cost k-vertex connected spanning subgraph. the first algorithm works on undirected graphs with at least 6k2 vertices and achieves an approximation factor of 6 times the kth harmonic number, which is $o(\log k)$. the second algorithm works on directed and undirected graphs. it gives an $o(\sqrt{ n /\keps})$-approximation algorithm for any $\keps > 0$ and $k \le (1-\keps)n$. the latter algorithm also extends to other problems in network design with vertex connectivity requirements. our main tools are setpair relaxations, a theorem of mader's (in the undirected case) and iterative rounding (general case).