Probabilistic construction of deterministic algorithms: approximating packing integer programs
From MaRDI portal
Recommendations
Cites work
- 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?)
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- A decomposition algorithm for circuit routing
- 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
- 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
- ``Integer-making theorems
Cited in
(98)- Scheduling in network flow shops
- On-line resource management with applications to routing and scheduling
- Removing randomness in parallel computation without a processor penalty
- The probabilistic method yields deterministic parallel algorithms
- Randomization, derandomization and antirandomization: Three games
- Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors
- The maximum clique problem
- Scheduling multicasts on unit-capacity trees and meshes.
- Staying safe and visible via message sharing in online social networks
- A closest vector problem arising in radiation therapy planning
- Geometric rounding: A dependent randomized rounding scheme
- Tight approximations for resource constrained scheduling and bin packing
- Improved algorithms via approximations of probability distributions
- Disjoint paths in sparse graphs
- Improved approximation algorithms for the Min-Max selecting items problem
- Faster min-max resource sharing in theory and practice
- Deterministic sampling algorithms for network design
- Randomized approximation of bounded multicovering problems
- Pseudo-Boolean optimization
- Listing graphs that satisfy first-order sentences
- Integer programming in VLSI design
- Single source unsplittable flows with arc-wise lower and upper bounds
- A tight bound on approximating arbitrary metrics by tree metrics
- Fast approximation of minimum multicast congestion – Implementation VERSUS Theory
- Approximation algorithms for general packing problems and their application to the multicast congestion problem
- Algorithmic construction of low-discrepancy point sets via dependent randomized rounding
- Approximation algorithms for geometric median problems
- Approximability of the robust representatives selection problem
- From Erdős to algorithms
- Reroute sequence planning in telecommunication networks and compact vector summation.
- Two-stage combinatorial optimization problems under risk
- An optimal convex hull algorithm in any fixed dimension
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
- Multiplying Pessimistic Estimators: Deterministic Approximation of Max TSP and Maximum Triangle Packing
- Stochastic set packing problem
- Approximations for the disjoint paths problem in high-diameter planar networks
- Thresholded covering algorithms for robust and max-min optimization
- Probabilistic optimal solution assessment for DCOPs
- Separating the communication complexity of truthful and nontruthful algorithms for combinatorial auctions
- Derandomized construction of combinatorial batch codes
- Independent sets in graphs with triangles
- Robust recoverable and two-stage selection problems
- Unbiased Matrix Rounding
- Cutting hyperplanes for divide-and-conquer
- Approximation algorithms for covering/packing integer programs
- Scheduling non-preemptible jobs to minimize peak demand
- scientific article; zbMATH DE number 1830719 (Why is no real title available?)
- Finding fixed point free elements and small bases in permutation groups
- On the approximability of clique and related maximization problems
- Approximation algorithms for the metric maximum clustering problem with given cluster sizes.
- Maximum renamable Horn sub-CNFs
- A guided tour of Chernoff bounds
- Matrix approximation and Tusnády's problem
- Approximation schemes for scheduling and covering on unrelated machines
- On complexity, representation and approximation of integral multicommodity flows
- Approximate and dynamic rank aggregation
- Approximation algorithms for multiprocessor scheduling under uncertainty
- Non-independent randomized rounding and coloring
- Prefix graphs and their applications
- Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra
- Near optimal solutions for maximum quasi-bicliques
- Improved algorithms for latency minimization in wireless networks
- Multicast Routing and Design of Sparse Connectors
- Minimizing the maximum flow time in batch scheduling
- Parallel approximation to high multiplicity scheduling problemsVIAsmooth multi-valued quadratic programming
- A linear time approximation algorithm for permutation flow shop scheduling
- The complexity of controlled selection
- Polynomial-time computation of exact correlated equilibrium in compact games
- Deterministic approximation algorithms for the maximum traveling salesman and maximum triangle packing problems
- Randomized rounding in the presence of a cardinality constraint
- Bipartite subgraphs
- Single source unsplittable flows with arc-wise lower and upper bounds
- Weighted fractional and integral k-matching in hypergraphs
- Greedily finding a dense subgraph
- Analysis of an asynchronous PRAM algorithm
- Computing sparse approximations deterministically
- On the approximation of the minimum disturbance \(p\)-facility location problem
- Algorithms as mechanisms: the price of anarchy of relax and round
- Bounds and constructions for the star-discrepancy via \(\delta\)-covers
- Task scheduling in networks
- An efficient distributed algorithm for constructing small dominating sets
- Medial axis based routing has constant load balancing factor
- Derandomization for sparse approximations and independent sets
- Neighborhood graphs and distributed Δ+1-coloring
- Component-by-component construction of low-discrepancy point sets of small size
- Algorithms for solving minimax scheduling problem
- Towards more practical linear programming-based techniques for algorithmic mechanism design
- On the parallel approximability of a subclass of quadratic programming.
- Some algorithms of solving minimax multiprocessor scheduling problem
- Entropy, Randomization, Derandomization, and Discrepancy
- Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number
- On routing in VLSI design and communication networks
- Deterministic discrepancy minimization
- Packing trees in communication networks
- Multiterminal global routing: A deterministic approximation scheme
- Improved parallel approximation of a class of integer programming problems
- Optimization with uniform size queries
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)
