【摘 要】
：
There are many optimization problems having the following common property:Given a total task consisting of many subtasks,the problem asks to find a solution to complete only part of these subtasks.Examples include the k-Forest problem and the k-Multicut p
【机 构】
：
School of Software,Shandong University,Jinan 250101,China
论文部分内容阅读
There are many optimization problems having the following common property:Given a total task consisting of many subtasks,the problem asks to find a solution to complete only part of these subtasks.Examples include the k-Forest problem and the k-Multicut problem,etc.These problems are called partial optimization problems,which are often NP-hard.In this paper,we systematically study the LP-rounding plus greed approach,a method to design approximation algorithms for partial optimization problems.The approach is simple,pow-erful and versatile.We show how to use this approach to de-sign approximation algorithms for the k-Forest problem,the k-Multicut problem,the k-Generalized connectivity problem,etc.
其他文献
Alkylation of benzene to value-added,high octane number and low toxic toluene and xylenes provides a way to lower benzene content in gasoline pool,and is hence a method to promote fuel quality.On the other hand,CO2 accumulation in the atmosphere causes gl
Production cost,capacitance,and electrode materials safety are the key factors to be concerned about for supercapacitors.In this work,a type of carbon nanosheets was produced through the carbonization of tripotassium citrate monohydrate and nitric acidifi
Advanced model-based control strategies,e.g.,model predictive control,can offer superior control of key process variables for multiple-input multiple-output sys-tems.The quality of the system model is critical to controller performance and should adequate
To study the dynamic behavior of a process,time-resolved data are collected at different time instants during each of a series of experiments,which are usually designed with the design of experiments or the design of dynamic experiments methodologies.For
The catalytic hydrogenation of carboxylic acid to alcohols is one of the important strategies for the conversion of biomass.Herein,a series of Ni-doped PtSn catalysts were prepared,characterized and studied in the hydrogenation of acetic acid.The Ni dopan
Solvent-based post-combustion capture tech-nologies have great potential for CO2 mitigation in traditional coal-fired power plants.Modelling and simula-tion provide a low-cost opportunity to evaluate perfor-mances and guide flexible operation.Composed by
Simulation is besides experimentation the major method for designing,analyzing and optimizing chemical processes.The ability of simulations to reflect real process behavior strongly depends on model quality.Validation and adaption of process models are us
Compared to conventional hyperthermia that is limited by low selectivity and severe side effects,nano-enabled hyperthermia yields great potentials to tackle these limitations for cancer treatment.Another major advance is the observation of immunological r
Dimethyl carbonate is an eco-friendly essential chemical that can be sustainably produced from CO2,which is available from carbon capture activities or can even be captured from the air.The rapid increase in dimethyl carbonate demand is driven by the fast
Flowsheet simulations of chemical processes on an industrial scale require the solution of large systems of nonlinear equations,so that solvability becomes a practical issue.Additional constraints from technical,economic,environmental,and safety considera