Probabilistic construction of deterministic algorithms: approximating packing integer programs

DOI10.1016/0022-0000(88)90003-7zbMath0659.90066OpenAlexW3011766368MaRDI QIDQ1112724

Publication date: 1988

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(88)90003-7

zbMATH Keywords

packing polynomial algorithm randomized rounding maximum multicommodity flow method of conditional probabilities vector selection

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Integer programming (90C10) Deterministic network models in operations research (90B10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Boolean programming (90C09)

Related Items

On the approximability of clique and related maximization problems, Randomization, derandomization and antirandomization: Three games, Single Source Unsplittable Flows with Arc-Wise Lower and Upper Bounds, Listing graphs that satisfy first-order sentences, Approximate and dynamic rank aggregation, The probabilistic method yields deterministic parallel algorithms, From Erdős to algorithms, Medial Axis Based Routing Has Constant Load Balancing Factor, Task scheduling in networks, Greedily finding a dense subgraph, Neighborhood graphs and distributed Δ+1-coloring, Weighted fractional and integral \(k\)-matching in hypergraphs, Near optimal solutions for maximum quasi-bicliques, Scheduling non-preemptible jobs to minimize peak demand, On the approximation of the minimum disturbance \(p\)-facility location problem, Independent sets in graphs with triangles, Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions, Tight approximations for resource constrained scheduling and bin packing, Computing sparse approximations deterministically, Matrix approximation and Tusnády's problem, Entropy, Randomization, Derandomization, and Discrepancy, Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions, Robust recoverable and two-stage selection problems, Approximation algorithms for multiprocessor scheduling under uncertainty, Derandomized Construction of Combinatorial Batch Codes, Thresholded covering algorithms for robust and max-min optimization, Deterministic Massively Parallel Connectivity, 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, Scheduling multicasts on unit-capacity trees and meshes., Prefix graphs and their applications, Parallel approximation to high multiplicity scheduling problemsVIAsmooth multi-valued quadratic programming, Component-by-component construction of low-discrepancy point sets of small size, Minimizing the maximum flow time in batch scheduling, A guided tour of Chernoff bounds, Multiterminal global routing: A deterministic approximation scheme, Maximum renamable Horn sub-CNFs, Improved approximation algorithms for the Min-Max selecting items problem, On complexity, representation and approximation of integral multicommodity flows, Deterministic approximation algorithms for the maximum traveling salesman and maximum triangle packing problems, Approximation algorithms for general packing problems and their application to the multicast congestion problem, Reroute sequence planning in telecommunication networks and compact vector summation., Fast approximation of minimum multicast congestion – Implementation VERSUS Theory, The complexity of controlled selection, An efficient distributed algorithm for constructing small dominating sets, Analysis of an asynchronous PRAM algorithm, On routing in VLSI design and communication networks, Improved parallel approximation of a class of integer programming problems, Towards more practical linear programming-based techniques for algorithmic mechanism design, On-line resource management with applications to routing and scheduling, Randomized approximation of bounded multicovering problems, Integer programming in VLSI design, Optimization with uniform size queries, Disjoint paths in sparse graphs, Pseudo-Boolean optimization, Approximation algorithms for geometric median problems, Cutting hyperplanes for divide-and-conquer, Improved algorithms for latency minimization in wireless networks, Faster min-max resource sharing in theory and practice, Deterministic sampling algorithms for network design, Some algorithms of solving minimax multiprocessor scheduling problem, Non-independent randomized rounding and coloring, On the parallel approximability of a subclass of quadratic programming., Algorithmic construction of low-discrepancy point sets via dependent randomized rounding, Deterministic discrepancy minimization, Stochastic set packing problem, Approximation schemes for scheduling and covering on unrelated machines, Probabilistic optimal solution assessment for DCOPs, Approximability of the robust representatives selection problem, Two-stage combinatorial optimization problems under risk, A tight bound on approximating arbitrary metrics by tree metrics, Algorithms for solving minimax scheduling problem, Packing trees in communication networks, Approximation algorithms for the metric maximum clustering problem with given cluster sizes., Multicast Routing and Design of Sparse Connectors, Approximations for the disjoint paths problem in high-diameter planar networks, Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors, Randomized Rounding in the Presence of a Cardinality Constraint, A linear time approximation algorithm for permutation flow shop scheduling, Algorithms as Mechanisms: The Price of Anarchy of Relax and Round, Bipartite subgraphs, Scheduling in network flow shops, Improved algorithms via approximations of probability distributions, Approximation algorithms for covering/packing integer programs, Bounds and constructions for the star-discrepancy via \(\delta\)-covers, 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, Unbiased Matrix Rounding, Polynomial-time computation of exact correlated equilibrium in compact games, Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number, The maximum clique problem, Single source unsplittable flows with arc-wise lower and upper bounds, Finding fixed point free elements and small bases in permutation groups

Cites Work