Search Results - subject:"approximation algorithms"

Did you mean: subject:"approximation algorithm" (11,480 results)

The generalized assignment problem with minimum quantities

Krumke, Sven O.; Thielen, Clemens - In: European Journal of Operational Research 228 (2013) 1, pp. 46-55

complexity results for different versions of the problem and give polynomial time exact algorithms and approximation algorithms … approximation algorithm (unless P=NP), even for the case of a single bin. This motivates to study dual approximation algorithms that …

Persistent link: https://www.econbiz.de/10011052812

Approximations for two variants of the Steiner tree problem in the Euclidean plane <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$${\mathbb{R}^2}$$</EquationSource> </InlineEquation>

Li, Jianping; Wang, Haiyan; Huang, Binchao; Lichen, Junran - In: Journal of Global Optimization 57 (2013) 3, pp. 783-801

problem, and then present two approximation algorithms with performance ratios 4 and 3.236 for the MCSPPSM problem …

Persistent link: https://www.econbiz.de/10010994113

Approximation algorithm for a class of global optimization problems

Locatelli, Marco - In: Journal of Global Optimization 55 (2013) 1, pp. 13-25

In this paper we develop and derive the computational cost of an <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$${\varepsilon}$$</EquationSource> </InlineEquation> -approximation algorithm for a class of global optimization problems, where a suitably defined composition of some ratio functions is minimized over a convex set. The result extends a previous one about a class...</equationsource></inlineequation>

Persistent link: https://www.econbiz.de/10010994132

An LP-based 2/3-approximation algorithm for the s-t path graph traveling salesman problem

Gao, Zhihan - In: Operations research letters 41 (2013) 6, pp. 615-617

Persistent link: https://www.econbiz.de/10010236087

Routing vehicles to minimize fuel consumption

Gaur, Daya Ram; Mudgal, Apurva; Singh, Rishi Ranjan - In: Operations research letters 41 (2013) 6, pp. 576-580

Persistent link: https://www.econbiz.de/10010236173

Single machine scheduling with job-dependent convex cost and arbitrary precedence constraints

Carrasco, Rodrigo A.; Iyengar, Garud; Stein, Cliff - In: Operations research letters 41 (2013) 5, pp. 436-441

Persistent link: https://www.econbiz.de/10010189892

On multiprocessor temperature-aware scheduling problems

Bampis, Evripidis; Letsios, Dimitrios; Lucarelli, Giorgio; … - In: Journal of scheduling 16 (2013) 5, pp. 529-538

Persistent link: https://www.econbiz.de/10010196449

Non-preemptive speed scaling

Antoniadis, Antonios; Huang, Chien-chung - In: Journal of scheduling 16 (2013) 4, pp. 385-394

Persistent link: https://www.econbiz.de/10009777788

Tight approximation bounds for combinatorial frugal coverage algorithms

Caragiannis, Ioannis; Kaklamanis, Christos; Kyropoulou, … - In: Journal of combinatorial optimization 26 (2013) 2, pp. 292-309

Persistent link: https://www.econbiz.de/10009778598

Approximations for monotone and nonmonotone submodular maximization with Knapsack constraints

Kulik, Ariel; Shachnai, Hadas; Tamir, Tami - In: Mathematics of operations research 38 (2013) 4, pp. 729-739

Persistent link: https://www.econbiz.de/10010210721