Skip to main content
eScholarship
Open Access Publications from the University of California

Scholarly Works (30 results)

  • Article
  • Peer Reviewed
UC Riverside Previously Published Works (2000)
In evaluating an algorithm, worst-case analysis can be overly pessimistic. Average-case analysis can be overly optimistic. An intermediate approach shows that an algorithm does well on a broad class of input distributions. E. Koutsoupias and C. H. Papadimitriou (1994, in "Proc. of the 35th IEEE Annual Symp. on Foundation of Computer Science," pp. 394-400, IEEE Press, New York) recently analyzed the least-recently-used (LRU) paging strategy in this manner, analyzing its performance on an input sequence generated by a so-called diffuse adversary - one that must choose each request probabilistically so that no page is chosen with probability more than some fixed ∈ > 0. They showed that LRU achieves the optimal competitive ratio (for deterministic on-line algorithms), but they did not determine the actual ratio. In this paper we estimate the optimal ratios within roughly a factor of two for both deterministic strategies and randomized strategies. Around the threshold ∈ ≈ 1/k (where k is the cache size), the optimal ratios are both Θ(In k). Below the threshold the ratios tend rapidly to O(1). Above the threshold the ratio is unchanged for randomized strategies but tends rapidly to Θ(k) for deterministic ones. We also show that the competitive ratios for First-in-first-out (FIFO) and Flush-when-full (FWF) are both k when ∈ ≥ 1/k. In contrast, the ratio for LRU is less than 2 In k + 4 when ∈ = 1/k. It is folklore that LRU outperforms FIFO in practice, but to date the only other variant of competitive analysis in which LRU has been shown to outperform FIFO is the access graph model. For completeness, we give an alternate proof of the optimality of LRU. © 2000 Academic Press.
    • Article
    • Peer Reviewed
    UC Riverside Previously Published Works (2014)
    We describe the first nearly linear-time approximation algorithms for explicitly given mixed packing/covering linear programs, and for (non-metric) fractional facility location. We also describe the first parallel algorithms requiring only near-linear total work and finishing in polylog time. The algorithms compute $(1+\epsilon)$-approximate solutions in time (and work) $O^*(N/\epsilon^2)$, where $N$ is the number of non-zeros in the constraint matrix. For facility location, $N$ is the number of eligible client/facility pairs.
      • Article
      • Peer Reviewed
      UC Riverside Previously Published Works (2010)
      We consider the problem of choosing Euclidean points to maximize the sum of their weighted pairwise distances, when each point is constrained to a ball centered at the origin. We derive a dual minimization problem and show strong duality holds (i.e., the resulting upper bound is tight) when some locally optimal configuration of points is affinely independent. We sketch a polynomial time algorithm for finding a near-optimal set of points.
        Cover page: A Bound on the Sum of Weighted Pairwise Distances of Points Constrained to Balls
        • Article
        • Peer Reviewed
        UC Riverside Previously Published Works (2013)
        We give a short proof that any comparison-based n^(1-epsilon)-approximation algorithm for the 1-dimensional Traveling Salesman Problem (TSP) requires Omega(n log n) comparisons.
          • Article
          • Peer Reviewed
          UC Riverside Previously Published Works (2015)
          We give a lower bound on the iteration complexity of a natural class of Lagrangianrelaxation algorithms for approximately solving packing/covering linear programs. We show that, given an input with m random 0/1-constraints on n variables, with high probability, any such algorithm requires Ω(ρ log(m)/∈2) iterations to compute a (1 + ∈)-approximate solution, where ρ is the width of the input. The bound is tight for a range of the parameters (m, n, ρ, ∈). The algorithms in the class include Dantzig-Wolfe decomposition, Benders' decomposition, Lagrangian relaxation as developed by Held and Karp for lower-bounding TSP, and many others (e.g., those by Plotkin, Shmoys, and Tardos and Grigoriadis and Khachiyan). To prove the bound, we use a discrepancy argument to show an analogous lower bound on the support size of (1 + ∈)-approximate mixed strategies for random two-player zero-sum 0/1-matrix games.
            Cover page: On the Number of Iterations for Dantzig--Wolfe Optimization and Packing-Covering Approximation Algorithms
            • Article
            • Peer Reviewed
            UC Riverside Previously Published Works (2011)
            This paper gives poly-logarithmic-round, distributed δ-approximation algorithms for covering problems with submodular cost and monotone covering constraints (Submodular-cost Covering). The approximation ratio δ is the maximum number of variables in any constraint. Special cases include Covering Mixed Integer Linear Programs (CMIP), and Weighted Vertex Cover (with δ = 2). Via duality, the paper also gives poly-logarithmic-round, distributed δ-approximation algorithms for Fractional Packing linear programs (where δ is the maximum number of constraints in which any variable occurs), and for Max Weighted c-Matching in hypergraphs (where δ is the maximum size of any of the hyperedges; for graphs δ = 2). The paper also gives parallel (RNC) 2-approximation algorithms for CMIP with two variables per constraint and Weighted Vertex Cover. The algorithms are randomized. All of the approximation ratios exactly match those of comparable centralized algorithms. © 2011 Springer-Verlag.
              • Thesis
              • Peer Reviewed
              UC Riverside Electronic Theses and Dissertations (2009)

              In this thesis we present sequential and distributed approximation algorithms for covering problems.

              First, we give a sequential $\ratio$-approximation algorithm for Monotone Covering, a generalization of many fundamental NP-hard covering problems. The approximation ratio $\ratio$ is the maximum number of variables on which any constraint depends. (For example, for vertex cover, $\ratio$ is 2.) The algorithm unifies, generalizes, and improves

              many previous algorithms for fundamental covering problems such as Vertex Cover, Set Cover, Facilities Location, and Covering Mixed-Integer Linear Programs with upper bound on the variables.

              The algorithm is also a $\ratio$-competitive algorithm for online Monotone Covering, which generalizes online versions of the above-mentioned covering problems as well as many fundamental online paging and caching problems. As such it also generalizes many classical online algorithms, including LRU, FIFO, FWF, Balance, Greedy-Dual, Greedy-Dual Size (a.k.a. Landlord), and algorithms for connection caching, where $\ratio$ is the cache size. It also gives new $\ratio$-competitive algorithms for upgradable variants of these problems, which model choosing the caching strategy and

              an appropriate hardware configuration (cache size, CPU, bus, network, etc.).

              Then we show distributed versions of the sequential algorithm.

              For Weighted Vertex Cover, we give a distributed 2-approximation algorithm taking $O(\log n)$ rounds. The algorithm generalizes to covering mixed integer linear programs (CMIP) with two variables per constraint ($\ratio=2$). For any Monotone Covering problem, we show

              a distributed $\ratio$-approximation algorithm taking

              $O(\log^2 |\calC|)$ rounds, where $|\calC|$ is the number of constraints.

              Last, we extend the distributed algorithms for covering to compute $\ratio$-approximate solutions for Fractional Packing and Maximum Weighted b-Matching in hypergraphs, where $\ratio$ is the maximum number of packing constraints in which a variable appears (for Maximum Weighted b-Matching $\ratio$ is the maximum edge degree --- for graphs $\ratio=2$).

                Cover page: Approximation Algorithms for Covering Problems
                • Article
                • Peer Reviewed
                UC Riverside Previously Published Works (2014)
                We give an approximation algorithm for fractional packing and covering linear programs (linear programs with non-negative coefficients). Given a constraint matrix with n non-zeros, r rows, and c columns, the algorithm (with high probability) computes feasible primal and dual solutions whose costs are within a factor of 1+ε of opt (the optimal cost) in time O((r+c)log(n)/ε2+n).
                  Cover page: A Nearly Linear-Time PTAS for Explicit Fractional Packing and Covering Linear Programs
                  • Article
                  • Peer Reviewed
                  UC Riverside Previously Published Works (2013)
                  This paper describes a simple greedy δ-approximation algorithm for any covering problem whose objective function is submodular and non-decreasing, and whose feasible region can be expressed as the intersection of arbitrary (closed upwards) covering constraints, each of which constrains at most δ variables of the problem. (A simple example is Vertex Cover, with δ=2.) The algorithm generalizes previous approximation algorithms for fundamental covering problems and online paging and caching problems. © 2012 Springer Science+Business Media, LLC.
                    • Article
                    • Peer Reviewed
                    UC Riverside Previously Published Works (2002)
                    This report presents notes from the first eight lectures of the class Many Models of Complexity taught by Laszlo Lovasz at Princeton University in the fall of 1990. The topic is evasiveness of graph properties: given a graph property, how many edges of the graph an algorithm must check in the worst case before it knows whether the property holds.
                      Top