scientific article

zbMath1368.68010MaRDI QIDQ3002852

No author found.

Publication date: 24 May 2011

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Collections of articles of miscellaneous specific interest (00B15) Proceedings, conferences, collections, etc. pertaining to computer science (68-06) Proceedings, conferences, collections, etc. pertaining to operations research and mathematical programming (90-06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items

Improved Lower Bounds on the Approximability of the Traveling Salesman Problem, New Algorithmic Results for Bin Packing and Scheduling, On the Complexity of the Star p-hub Center Problem with Parameterized Triangle Inequality, On the Parameterized Complexity of the Expected Coverage Problem, Primal-dual approximation algorithms for feedback problems in planar graphs, APPROXIMATION ALGORITHMS FOR FLEXIBLE JOB SHOP PROBLEMS, A Spectral Approach to Network Design, Deterministic Random Walks for Rapidly Mixing Chains, Intractability of assembly sequencing: Unit disks in the plane, Scheduling equal-length jobs with arbitrary sizes on uniform parallel batch machines, Pseudorandom sets in Grassmann graph have near-perfect expansion, Determining the Minimum Number of Warehouses and their Space-Size for Storing Compatible Items, Nash welfare guarantees for fair and efficient coverage, The k-centre problem for classes of cyclic words, Optimal shape of a blob, Introduction to Testing Graph Properties, Fast Approximation Methods for Online Scheduling of Outpatient Procedure Centers, A more fine‐grained complexity analysis of finding the most vital edges for undirected shortest paths, Fully-Dynamic Bin Packing with Little Repacking, Fast and Deterministic Approximations for k-Cut., ON 4-EDGE COLORING OF CUBIC GRAPHS CONTAINING “SMALL” NON-PLANAR SUBGRAPHS, Online bin packing of squares and cubes, Improved Approximation Algorithm for the Combination of Parallel Machine Scheduling and Vertex Cover, Testing Expansion in Bounded-Degree Graphs, Generalized loop‐erased random walks and approximate reachability, On the maximum edge-pair embedding bipartite matching, Online bin packing of squares and cubes, Unnamed Item, Transitive-Closure Spanners: A Survey, EPTAS for load balancing problem on parallel machines with a non-renewable resource, Object Caching for Queries and Updates, An improved mechanism for selfish bin packing, On-line scheduling of parallel jobs with runtime restrictions, Online request server matching, Hardness and methods to solve CLIQUE, Inapproximability of finding maximum hidden sets on polygons and terrains, Deadline TSP, Fractional path coloring in bounded degree trees with applications, Finding large degree-anonymous subgraphs is hard, Minimum membership covering and hitting, The Priority k-Median Problem, Clustering Using Objective Functions and Stochastic Search, AN OPTIMAL REBUILDING STRATEGY FOR AN INCREMENTAL TREE PROBLEM, A Survey on Approximation Algorithms for Scheduling with Machine Unavailability, Differential approximation of NP-hard problems with equal size feasible solutions, Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances, Computing spectral bounds of the Heisenberg ferromagnet from geometric considerations, Approximation algorithms in combinatorial scientific computing, The number of matchings in random graphs, Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph, Sequential stratified splitting for efficient Monte Carlo integration, Constrained k-Center Problem on a Convex Polygon, How to Keep an Eye on Small Things, Unnamed Item, Direct routing: Algorithms and complexity, A faster combinatorial approximation algorithm for scheduling unrelated parallel machines, Dynamic bin packing of unit fractions items, Primal-dual approximation algorithms for the prize-collecting Steiner tree problem, Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms, Maximizing the guarded boundary of an Art Gallery is APX-complete, The polygon burning problem, On some optimization problems in molecular biology, Computing the asymptotic worst-case of bin packing lower bounds, Mixing of the Glauber dynamics for the ferromagnetic Potts model, A 2-approximation NC algorithm for connected vertex cover and tree cover, Improved MaxSAT Algorithms for Instances of Degree 3, A primal-dual approximation algorithm for partial vertex cover: Making educated guesses, Discrete dynamical system approaches for Boolean polynomial optimization, Unnamed Item, Approximation and online algorithms for multidimensional bin packing: a survey, A landscape-based analysis of fixed temperature and simulated annealing, Complexity of constrained sensor placement problems for optimal observability, Fast Distributed Approximation for TAP and 2-Edge-Connectivity, An approximation algorithm for the dynamic facility location problem with outliers, A tight linear time \(\frac{13}{12}\)-approximation algorithm for the \(P2 || C_{\max}\) problem, Resolution and linear CNF formulas: improved \((n,3)\)-\textsc{MaxSAT} algorithms, Breaking symmetries to rescue sum of squares in the case of makespan scheduling, Approximation of the quadratic set covering problem, Approximation algorithm for minimum weight connected-\(k\)-subgraph cover, Pruning 2-connected graphs, A competitive analysis for balanced transactional memory workloads, Maximum subset intersection, The evolution of rectangular bin packing problem -- a review of research topics, applications, and cited papers, Scheduling jobs with sizes and delivery times on identical parallel batch machines, Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost, A lower bound of \(1+\varphi \) for truthful scheduling mechanisms, Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization, The community structure of human cellular signaling network, Critical edges for the assignment problem: complexity and exact resolution, A simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithms, Minimum propositional proof length is NP-hard to linearly approximate, Fair Scheduling via Iterative Quasi-Uniform Sampling, An analysis of totally clairvoyant scheduling, Two-dimensional bin packing with one-dimensional resource augmentation, Primal-Dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar Graphs, Fast distributed approximation for TAP and 2-edge-connectivity, Online bin packing with arbitrary release times, A fast asymptotic approximation scheme for bin packing with rejection, Approximation algorithms for constructing some required structures in digraphs, The freight consolidation and containerization problem, A cutting plane approach for integrated planning and scheduling, Measuring instance difficulty for combinatorial optimization problems, Paired-domination problem on distance-hereditary graphs, Minimizing makespan on a single batching machine with release times and non-identical job sizes, Finding minimum hidden guard sets in polygons --- tight approximability results, Exponential penalty function control of loss networks, The approximability of non-Boolean satisfiability problems and restricted integer programming, Bounded-hops power assignment in ad hoc wireless networks, Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs, Polynomial approximation algorithms with performance guarantees: an introduction-by-example, Core instances for testing: a case study, Batched bin packing, On complexity of unconstrained hyperbolic 0--1 programming problems, Selfish colorful bin packing games, A class of node based bottleneck improvement problems, Graph spanners: a tutorial review, A new family of proximity graphs: class cover catch digraphs, ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES, APPLICATION PLACEMENT ON A CLUSTER OF SERVERS, Dynamic programming optimization in line of sight networks, Scheduling equal length jobs with eligibility restrictions, Design and performance evaluation of communication algorithms in multihop wireless networks with multiple channels, Line planning, path constrained network flow and inapproximability, Complete-subgraph-transversal-sets problem on bounded treewidth graphs, A hybrid evolutionary algorithm for the offline Bin Packing Problem, On the parametrized complexity of Read-once refutations in UTVPI+ constraint systems, An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses, Online Non-preemptive Scheduling to Optimize Max Stretch on a Single Machine, In a World of P=BPP, Introduction to Testing Graph Properties, Randomness and Computation, Contemplations on Testing Graph Properties, Regret in the on-line decision problem, ON RECTANGULAR COVERING PROBLEMS, Efficient approximation algorithms for maximum coverage with group budget constraints, Strong lower bounds for the prize collecting Steiner problem in graphs, Isolation branching: a branch and bound algorithm for the \(k \)-terminal cut problem, Approximation algorithms for constructing required subgraphs using stock pieces of fixed length, Scheduling orders for multiple product types with due date related objectives, THE COMPUTATIONAL COMPLEXITY OF AVOIDING FORBIDDEN SUBMATRICES BY ROW DELETIONS, Fully polynomial time \((\Sigma,\Pi)\)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs, On approximation of max-vertex-cover, A reduction technique for weighted grouping problems, A FAST IMPLEMENTATION OF THE ISODATA CLUSTERING ALGORITHM, Optimization with randomized search heuristics -- the (A)NFL theorem, realistic scenarios, and difficult functions., Obtaining matrices with the consecutive ones property by row deletions, An improved approximation algorithm for vertex cover with hard capacities, 2-approximation algorithm for minmax absolute maximum lateness scheduling-location problem, Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings, An Empirical Study of MAX-2-SAT Phase Transitions, Approximating the optimal sequence of acquisitions and sales with a capped budget, Primal-dual approximation algorithms for a packing-covering pair of problems, Offline black and white bin packing, Approximability of guarding weak visibility polygons, Vehicle scheduling under the warehouse-on-wheels policy, Geometric partitioning and robust ad-hoc network design, An APTAS for bin packing with clique-graph conflicts, Complexity of core allocation for the bin packing game, Truthful mechanism design for multidimensional scheduling via cycle monotonicity, Approximation algorithms for the TSP with sharpened triangle inequality, On the multi-radius cover problem, On approximation algorithms for the minimum satisfiability problem, Approximation algorithms for constructing specific subgraphs with minimum number of length-bounded stock pieces, A two-phase algorithm for the cyclic inventory routing problem, Bin packing and cutting stock problems: mathematical models and exact algorithms, The hardness of approximate optima in lattices, codes, and systems of linear equations, An approximation algorithm for state minimization in 2-MDFAs, Maximizing data locality in distributed systems, Fast machine reassignment, An exact approach based on a new pseudo-polynomial network flow model for integrated planning and scheduling, On some network design problems with degree constraints, The complexity of probabilistic lobbying, An efficient fixed-parameter algorithm for 3-hitting set, Approximation algorithms for Hamming clustering problems, Multiple voting location and single voting location on trees, On approximating complex quadratic optimization problems via semidefinite programming relaxations, Dynamic bin packing with unit fraction items revisited, Total variation discrepancy of deterministic random walks for ergodic Markov chains, Approximability and inapproximability of the star \(p\)-hub center problem with parameterized triangle inequality, Bin packing under linear constraints, Maximum coverage problem with group budget constraints, A novel parameterised approximation algorithm for \textsc{minimum vertex cover}, Solving min ones 2-SAT as fast as vertex cover, Optimal cuts and partitions in tree metrics in polynomial time, PCPs via the low-degree long code and hardness for constrained hypergraph coloring, Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms, Complexity of majority monopoly and signed domination problems, Scheduling multicasts on unit-capacity trees and meshes., Approximation algorithms for scheduling jobs with release times and arbitrary sizes on batch machines with non-identical capacities, Irreversible Monte Carlo algorithms for efficient sampling, Uniform unweighted set cover: the power of non-oblivious local search, An approximation algorithm for scheduling two parallel machines with capacity constraints., Competitive ratio of list scheduling on uniform machines and randomized heuristics, A mean field approach for optimization in discrete time, An approximation algorithm for soft capacitated \(k\)-facility location problem, LP-relaxations for tree augmentation, A theory and algorithms for combinatorial reoptimization, A primal-dual approximation algorithm for the vertex cover \(P^3\) problem, An improved lower bound for approximating minimum GCD multiplier in \(\ell _\infty \) norm (GCDM\(_\infty\)), On approximability of linear ordering and related NP-optimization problems on graphs., Reroute sequence planning in telecommunication networks and compact vector summation., A generalization of Nemhauser and Trotter's local optimization theorem, On the algebraic complexity of some families of coloured Tutte polynomials, Voronoi game on graphs, Hardness of optimal spaced seed design, Simultaneous matchings: Hardness and approximation, Active influence spreading in social networks, Group-strategyproof cost sharing mechanisms for makespan and other scheduling problems, Inapproximability and approximability of minimal tree routing and coloring, Station assignment with reallocation, Scheduling of parallel machines with sequence-dependent batches and product incompatibilities in an automotive glass facility, On a posterior evaluation of a simple greedy method for set packing, Large gaps in one-dimensional cutting stock problems, Disruption recovery at airports: integer programming formulations and polynomial time algorithms, \(\varepsilon \)-optimization schemes and \(L\)-bit precision: alternative perspectives for solving combinatorial optimization problems, On optimal approximability results for computing the strong metric dimension, Dealing with 4-variables by resolution: an improved MaxSAT algorithm, Two-agent scheduling on a single parallel-batching machine with equal processing time and non-identical job sizes, Stochastic enumeration method for counting trees, The price of optimum: complexity and approximation for a matching game, Colocating tasks in data centers using a side-effects performance model, Approximation algorithms for highly connected multi-dominating sets in unit disk graphs, A note on the minimum bounded edge-partition of a tree, Minimum vertex cover in rectangle graphs, Dynamic programming based algorithms for set multicover and multiset multicover problems, Approximation algorithm for the kinetic robust \(k\)-center problem, The checkpoint problem, Exact and approximate equilibria for optimal group network formation, Approximability of clique transversal in perfect graphs, Efficient approximation algorithms for clustering point-sets, On \(k\)-connectivity problems with sharpened triangle inequality, Approximation algorithms for the partition vertex cover problem, Approximating the maximum clique minor and some subgraph homeomorphism problems, A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs, A relax-and-cut algorithm for the prize-collecting Steiner problem in graphs, Approximation algorithms for a hierarchically structured bin packing problem, On the maximum size of a minimal \(k\)-edge connected augmentation, There is no EPTAS for two-dimensional knapsack, A lower bound for scheduling mechanisms, On the minimum label spanning tree problem, PTAS for connected vertex cover in unit disk graphs, Interactive and probabilistic proof-checking, Classification using proximity catch digraphs, APX-hardness of domination problems in circle graphs, New and improved level heuristics for the rectangular strip packing and variable-sized bin packing problems, Approximating minimum feedback vertex sets in hypergraphs, Fixed topology alignment with recombination, Linear time-approximation algorithms for bin packing, On-line scheduling revisited, Evolutionary local search for the edge-biconnectivity augmentation problem, Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem., The hardness of placing street names in a Manhattan type map, Drawing graphs by eigenvectors: theory and practice, The generalized assignment problem with minimum quantities