Probabilistic construction of deterministic algorithms: approximating packing integer programs
From MaRDI portal
A matrix \(C_{n\times r}\), \(c_{ij}\in [0,1]\) and a vector \(p=(p_ 1,...,p_ r)\) are given. An integer vector \(q=(q_ 1,...,q_ r)\) that approximates \(p\) is computed. Every coordinate of the vector \(\Delta =C(p- q)\) has to be ``small in absolute value. By methods taken from probability theory the author proves the theorem: there exists a vector q such that \(\Delta_ i\leq s_ i\) \(D(s_ i,1/2n)\) for \(s_ i=(c_ i,p)\), where \[ D(m,x)\leq (e-1)(\frac{\ln 1/x}{m})^{1/2},\quad if\quad m>\ln \quad 1/x, \] and \[ D(m,x)\leq \frac{e \ln 1/x}{m \ln ((e \ln 1/x)/m)}, \] otherwise. A deterministic polynomial algorithm is proposed for finding such a vector \(q\). It traces a search tree from a root to some leaf without backtracking. At the next node a component \(q_ i\) is determined by the use of estimates for \(q_ i=0\) and \(q_ i=1\). The procedure, called ``method of conditional probabilities, is applied to vector selection problems, packing problems and maximum multicommodity flow.
Recommendations
Cites work
- ``Integer-making theorems
- A decomposition algorithm for circuit routing
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- A new polynomial-time algorithm for linear programming
- Balancing families of sets
- Fast probabilistic algorithms for Hamiltonian circuits and matchings
- Global wire routing in two-dimensional arrays
- scientific article; zbMATH DE number 3482343 (Why is no real title available?)
- scientific article; zbMATH DE number 3571502 (Why is no real title available?)
- scientific article; zbMATH DE number 3793772 (Why is no real title available?)
- On the Complexity of Timetable and Multicommodity Flow Problems
- On the ratio of optimal integral and fractional covers
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- Six Standard Deviations Suffice
Cited in
(only showing first 100 items - show all)- Packing trees in communication networks
- The complexity of controlled selection
- Analysis of an asynchronous PRAM algorithm
- Integer programming in VLSI design
- Approximation algorithms for geometric median problems
- Cutting hyperplanes for divide-and-conquer
- Approximations for the disjoint paths problem in high-diameter planar networks
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Removing randomness in parallel computation without a processor penalty
- An optimal convex hull algorithm in any fixed dimension
- The maximum clique problem
- Randomization, derandomization and antirandomization: Three games
- Listing graphs that satisfy first-order sentences
- The probabilistic method yields deterministic parallel algorithms
- From Erdős to algorithms
- Weighted fractional and integral k-matching in hypergraphs
- On the approximation of the minimum disturbance \(p\)-facility location problem
- Independent sets in graphs with triangles
- Tight approximations for resource constrained scheduling and bin packing
- Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra
- Scheduling multicasts on unit-capacity trees and meshes.
- Reroute sequence planning in telecommunication networks and compact vector summation.
- Improved algorithms via approximations of probability distributions
- Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number
- Minimizing the maximum flow time in batch scheduling
- Approximability of the robust representatives selection problem
- Approximation algorithms for the metric maximum clustering problem with given cluster sizes.
- On the approximability of clique and related maximization problems
- Approximate and dynamic rank aggregation
- Computing sparse approximations deterministically
- Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
- Maximum renamable Horn sub-CNFs
- On complexity, representation and approximation of integral multicommodity flows
- Deterministic discrepancy minimization
- Single source unsplittable flows with arc-wise lower and upper bounds
- Some algorithms of solving minimax multiprocessor scheduling problem
- Two-stage combinatorial optimization problems under risk
- Polynomial-time computation of exact correlated equilibrium in compact games
- Finding fixed point free elements and small bases in permutation groups
- Near optimal solutions for maximum quasi-bicliques
- Robust recoverable and two-stage selection problems
- Improved approximation algorithms for the Min-Max selecting items problem
- Deterministic approximation algorithms for the maximum traveling salesman and maximum triangle packing problems
- Non-independent randomized rounding and coloring
- Approximation schemes for scheduling and covering on unrelated machines
- Bipartite subgraphs
- Scheduling in network flow shops
- Approximation algorithms for covering/packing integer programs
- Bounds and constructions for the star-discrepancy via \(\delta\)-covers
- Scheduling non-preemptible jobs to minimize peak demand
- Randomized rounding in the presence of a cardinality constraint
- Derandomized construction of combinatorial batch codes
- Unbiased Matrix Rounding
- Medial axis based routing has constant load balancing factor
- Parallel approximation to high multiplicity scheduling problemsVIAsmooth multi-valued quadratic programming
- Component-by-component construction of low-discrepancy point sets of small size
- Derandomization for sparse approximations and independent sets
- Multiplying Pessimistic Estimators: Deterministic Approximation of Max TSP and Maximum Triangle Packing
- Multicast Routing and Design of Sparse Connectors
- Thresholded covering algorithms for robust and max-min optimization
- Staying safe and visible via message sharing in online social networks
- Geometric rounding: A dependent randomized rounding scheme
- A closest vector problem arising in radiation therapy planning
- scientific article; zbMATH DE number 1305459 (Why is no real title available?)
- On-line resource management with applications to routing and scheduling
- scientific article; zbMATH DE number 1830719 (Why is no real title available?)
- scientific article; zbMATH DE number 852056 (Why is no real title available?)
- Algorithms as mechanisms: the price of anarchy of relax and round
- Single source unsplittable flows with arc-wise lower and upper bounds
- Task scheduling in networks
- Greedily finding a dense subgraph
- Neighborhood graphs and distributed Δ+1-coloring
- Towards more practical linear programming-based techniques for algorithmic mechanism design
- Separating the communication complexity of truthful and nontruthful algorithms for combinatorial auctions
- Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors
- An efficient distributed algorithm for constructing small dominating sets
- Optimization with uniform size queries
- Entropy, Randomization, Derandomization, and Discrepancy
- Improved algorithms for latency minimization in wireless networks
- Faster min-max resource sharing in theory and practice
- Deterministic sampling algorithms for network design
- Fast approximation of minimum multicast congestion – Implementation VERSUS Theory
- A tight bound on approximating arbitrary metrics by tree metrics
- On the parallel approximability of a subclass of quadratic programming.
- Approximation algorithms for multiprocessor scheduling under uncertainty
- Prefix graphs and their applications
- Improved parallel approximation of a class of integer programming problems
- Randomized approximation of bounded multicovering problems
- Enclosing points with geometric objects
- Pseudo-Boolean optimization
- Bounds on mixing time for time-inhomogeneous Markov chains
- Algorithmic construction of low-discrepancy point sets via dependent randomized rounding
- Stochastic set packing problem
- Probabilistic optimal solution assessment for DCOPs
- A nearly optimal deterministic online algorithm for non-metric facility location
- Online disjoint set covers: randomization is not necessary
- Optimal (degree+1)-coloring in congested clique
- Algorithms for solving minimax scheduling problem
- A linear time approximation algorithm for permutation flow shop scheduling
- Matrix approximation and Tusnády's problem
This page was built for publication: Probabilistic construction of deterministic algorithms: approximating packing integer programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1112724)
