Relevant bibliographies by topics / Parameterized approximation

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Book chapters
  4. Conference papers

Academic literature on the topic 'Parameterized approximation'

Author: Grafiati
Published: 4 June 2021
Last updated: 4 February 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Parameterized approximation.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Parameterized approximation"

1

Marx, D. "Parameterized Complexity and Approximation Algorithms." Computer Journal 51, no. 1 (2007): 60–78. http://dx.doi.org/10.1093/comjnl/bxm048.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Zehavi, Meirav. "Parameterized approximation algorithms for packing problems." Theoretical Computer Science 648 (October 2016): 40–55. http://dx.doi.org/10.1016/j.tcs.2016.08.004.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Fellows, Michael R., Ariel Kulik, Frances Rosamond, and Hadas Shachnai. "Parameterized approximation via fidelity preserving transformations." Journal of Computer and System Sciences 93 (May 2018): 30–40. http://dx.doi.org/10.1016/j.jcss.2017.11.001.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Fomin, Fedor V., Petr A. Golovach, and Fahad Panolan. "Parameterized low-rank binary matrix approximation." Data Mining and Knowledge Discovery 34, no. 2 (2020): 478–532. http://dx.doi.org/10.1007/s10618-019-00669-5.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Downey, Rodney G., Michael R. Fellows, Catherine McCartin, and Frances Rosamond. "Parameterized approximation of dominating set problems." Information Processing Letters 109, no. 1 (2008): 68–70. http://dx.doi.org/10.1016/j.ipl.2008.09.017.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Chen, Jianer, Xiuzhen Huang, Iyad A. Kanj, and Ge Xia. "Polynomial time approximation schemes and parameterized complexity." Discrete Applied Mathematics 155, no. 2 (2007): 180–93. http://dx.doi.org/10.1016/j.dam.2006.04.040.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Cygan, Marek, Łukasz Kowalik, Arkadiusz Socała, and Krzysztof Sornat. "Approximation and Parameterized Complexity of Minimax Approval Voting." Journal of Artificial Intelligence Research 63 (November 21, 2018): 495–513. http://dx.doi.org/10.1613/jair.1.11253.

Full text
Abstract:
We present three results on the complexity of Minimax Approval Voting. First, we study Minimax Approval Voting parameterized by the Hamming distance d from the solution to the votes. We show Minimax Approval Voting admits no algorithm running in time O*(2o(d log d)), unless the Exponential Time Hypothesis (ETH) fails. This means that the O*(d2d) algorithm of Misra, Nabeel and Singh is essentially optimal. Motivated by this, we then show a parameterized approximation scheme, running in time O*((3/ε)2d), which is essentially tight assuming ETH. Finally, we get a new polynomial-time randomized ap
APA, Harvard, Vancouver, ISO, and other styles
8

Bazgan, Cristina, Florent Foucaud, and Florian Sikora. "Parameterized and approximation complexity of Partial VC Dimension." Theoretical Computer Science 766 (April 2019): 1–15. http://dx.doi.org/10.1016/j.tcs.2018.09.013.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Jansen, Klaus. "Parameterized Approximation Scheme for the Multiple Knapsack Problem." SIAM Journal on Computing 39, no. 4 (2010): 1392–412. http://dx.doi.org/10.1137/080731207.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Chitnis, Rajesh, Andreas Emil Feldmann, and Pasin Manurangsi. "Parameterized Approximation Algorithms for Bidirected Steiner Network Problems." ACM Transactions on Algorithms 17, no. 2 (2021): 1–68. http://dx.doi.org/10.1145/3447584.

Full text
Abstract:
The D irected S teiner N etwork (DSN) problem takes as input a directed graph G =( V , E ) with non-negative edge-weights and a set D ⊆ V × V of k demand pairs. The aim is to compute the cheapest network N⊆ G for which there is an s\rightarrow t path for each ( s , t )∈ D. It is known that this problem is notoriously hard, as there is no k 1/4− o (1) -approximation algorithm under Gap-ETH, even when parametrizing the runtime by k [Dinur & Manurangsi, ITCS 2018]. In light of this, we systematically study several special cases of DSN and determine their parameterized approximability for the
APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic "Parameterized approximation"

1

Huang, Xiuzhen. "Parameterized complexity and polynomial-time approximation schemes." Texas A&M University, 2004. http://hdl.handle.net/1969.1/1446.

Full text
Abstract:
According to the theory of NPcompleteness, many problems that have important realworld applications are NPhard. This excludes the possibility of solving them in polynomial time unless P=NP. A number of approaches have been proposed in dealing with NPhard problems, among them are approximation algorithms and parameterized algorithms. The study of approximation algorithms tries to find good enough solutions instead of optimal solutions in polynomial time, while parameterized algorithms try to give exact solutions when a natural parameter is small. In this thesis, we study the structural
APA, Harvard, Vancouver, ISO, and other styles
2

Jahundovics, Vladislavs. "Automatic Verification of Parameterized Systems by Over-Approximation." Licentiate thesis, Linköpings universitet, Institutionen för datavetenskap, 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-121776.

Full text
Abstract:
This thesis presents a completely automatic verification framework to check safety properties of parameterized systems. A parameterized system is a family of finite state systems where every system consists of a finite number of processes running in parallel the same algorithm. All the systems in the family differ only in the number of the processes and, in general, the number of systems in a family may be unbounded. Examples of parameterized systems are communication protocols, mutual exclusion protocols, cache coherence protocols, distributed algorithms etc. Model-checking of finite state sy
APA, Harvard, Vancouver, ISO, and other styles
3

Katsikarelis, Ioannis. "Structurally Parameterized Tight Bounds and Approximation for Generalizations of Independence and Domination." Thesis, Paris Sciences et Lettres (ComUE), 2019. http://www.theses.fr/2019PSLED048.

Full text
Abstract:
Nous nous concentrons sur les problèmes (k, r)-CENTER et d-SCATTERED SET qui généralisent les concepts de domination et indépendance des sommets, sur les distances plus grandes.Dans la première partie, nous examinons le paramétrage standard, ainsi que les paramètres des graphes mesurant la structure de l’entrée. Nous proposons des résultats qui montrent qu’il n’existe pas d’algorithme avec un temps d’exécution inférieur à certaines limites, si l’hypothèse du temps exponentiel est vraie, nous produisons des algorithmes de complexité essentiellement optimale qui correspondent à ces limites et no
APA, Harvard, Vancouver, ISO, and other styles
4

Rezine, Ahmed. "Parameterized Systems : Generalizing and Simplifying Automatic Verification." Doctoral thesis, Uppsala universitet, Avdelningen för datorteknik, 2008. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-8587.

Full text
Abstract:
In this thesis we propose general and simple methods for automatic verification of parameterized systems. These are systems consisting of an arbitrary number of identical processes or components. The number of processes defines the size of the system. A parameterized system may be regarded as an infinite family of instances, namely one for each size. The aim is to perform a parameterized verification, i.e. to verify that behaviors produced by all instances, regardless of their size, comply with some safety or liveness property. In this work, we describe three approaches to parameterized verifi
APA, Harvard, Vancouver, ISO, and other styles
5

Ben, Henda Noomene. "Infinite-state Stochastic and Parameterized Systems." Doctoral thesis, Uppsala University, Department of Information Technology, 2008. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-8915.

Full text
Abstract:
<p>A major current challenge consists in extending formal methods in order to handle infinite-state systems. Infiniteness stems from the fact that the system operates on unbounded data structure such as stacks, queues, clocks, integers; as well as parameterization.</p><p>Systems with unbounded data structure are natural models for reasoning about communication protocols, concurrent programs, real-time systems, etc. While parameterized systems are more suitable if the system consists of an arbitrary number of identical processes which is the case for cache coherence protocols, distributed algor
APA, Harvard, Vancouver, ISO, and other styles
6

Watel, Dimitri. "Approximation de l'arborescence de Steiner." Thesis, Versailles-St Quentin en Yvelines, 2014. http://www.theses.fr/2014VERS0025/document.

Full text
Abstract:
Dans un graphe orienté contenant un nœud appelé racine, un sous ensemble de nœuds appelés terminaux et une pondération sur les arcs, le problème de l’arborescence de Steiner (DST) consiste en la recherche d’une arborescence de poids minimum contenant pour chaque terminal un chemin de la racine vers ce terminal. Ce problème est NP-Complet. Cette thèse se penche sur l’étude de l’approximabilité de ce problème. Sauf si P=NP, il n’existe pas pour ce problème d’approximation de rapport constant ou logarithmique en k, oú k est le nombre de terminaux. Le plus petit rapport d’approximation connu est O
APA, Harvard, Vancouver, ISO, and other styles
7

Bonnet, Edouard. "Résultats Positifs et Négatifs en Approximation et Complexité Paramétrée." Thesis, Paris 9, 2014. http://www.theses.fr/2014PA090040/document.

Full text
Abstract:
De nombreux problèmes de la vie réelle sont NP-Difficiles et ne peuvent pas être résolus en temps polynomial. Deux paradigmes notables pour les résoudre quand même sont: l'approximation et la complexité paramétrée. Dans cette thèse, on présente une nouvelle technique appelée "gloutonnerie-Pour-La-Paramétrisation". On l'utilise pour établir ou améliorer la complexité paramétrée de nombreux problèmes et également pour obtenir des algorithmes paramétrés pour des problèmes à cardinalité contrainte sur les graphes bipartis. En vue d'établir des résultats négatifs sur l'approximabilité en temps sous
APA, Harvard, Vancouver, ISO, and other styles
8

Duvillié, Guillerme. "Approximation, complexité paramétrée et stratégies de résolution de problèmes d'affectation multidimensionnelle." Thesis, Montpellier, 2016. http://www.theses.fr/2016MONTT321/document.

Full text
Abstract:
Au cours de la thèse, nous nous sommes intéressés aux problèmes d'empilement de wafers. Ces problèmes apparaissent lors de la fabrication de processeurs en 3 dimensions. Au cours du processus de fabrication, les puces électroniques doivent être empilées les unes sur les autres. Jusqu'à peu, ces dernières, une fois gravées sur des plaques de silicium appelées wafers, étaient découpées, puis triées afin d'écarter les puces défectueuses et enfin assemblées les unes entre elles.Cependant empiler les wafers plutôt que les puces présente de nombreux avantages techniques et financiers. Naturellement,
APA, Harvard, Vancouver, ISO, and other styles
9

Mortada, Hassan. "Separation of parameterized and delayed sources : application to spectroscopic and multispectral data." Thesis, Strasbourg, 2018. http://www.theses.fr/2018STRAD051/document.

Full text
Abstract:
Ce travail est motivé par la spectroscopie de photoélectrons et l'étude de la cinématique des galaxies où les données correspondent respectivement à une séquence temporelle de spectres et à une image multispectrale. L'objectif est d'estimer les caractéristiques (amplitude, position spectrale et paramètre de forme) des raies présentes dans les spectres, ainsi que leur évolution au sein des données. Dans les applications considérées, cette évolution est lente puisque deux spectres voisins sont souvent très similaires : c'est une connaissance a priori qui sera prise en compte dans les méthodes dé
APA, Harvard, Vancouver, ISO, and other styles
10

Watrigant, Rémi. "Approximation et complexité paramétrée de problèmes d’optimisation dans les graphes : partitions et sous-graphes." Thesis, Montpellier 2, 2014. http://www.theses.fr/2014MON20100/document.

Full text
Abstract:
La théorie de la NP-complétude nous apprend que pour un certain nombre de problèmes d'optimisation, il est vain d'espérer un algorithme efficace calculant une solution optimale. Partant de ce constat, un moyen pour contourner cet obstacle est de réaliser un compromis sur chacun de ces critères, engendrant deux approches devenues classiques. La première, appelée approximation polynomiale, consiste à développer des algorithmes efficaces et retournant une solution proche d'une solution optimale. La seconde, appelée complexité paramétrée, consiste à développer des algorithmes retou
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Parameterized approximation"

1

Downey, Rodney G., and Michael R. Fellows. "Parameterized Approximation." In Texts in Computer Science. Springer London, 2013. http://dx.doi.org/10.1007/978-1-4471-5559-1_31.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Downey, Rodney G., Michael R. Fellows, and Catherine McCartin. "Parameterized Approximation Problems." In Parameterized and Exact Computation. Springer Berlin Heidelberg, 2006. http://dx.doi.org/10.1007/11847250_11.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Downey, R. G., and M. R. Fellows. "Optimization Problems, Approximation Schemes, and Their Relation with FPT." In Parameterized Complexity. Springer New York, 1999. http://dx.doi.org/10.1007/978-1-4612-0515-9_4.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Guo, Jiong, Iyad Kanj, and Stefan Kratsch. "Safe Approximation and Its Relation to Kernelization." In Parameterized and Exact Computation. Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-28050-4_14.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Brankovic, Ljiljana, and Henning Fernau. "Parameterized Approximation Algorithms for Hitting Set." In Approximation and Online Algorithms. Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-29116-6_6.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Cai, Liming, and Xiuzhen Huang. "Fixed-Parameter Approximation: Conceptual Framework and Approximability Results." In Parameterized and Exact Computation. Springer Berlin Heidelberg, 2006. http://dx.doi.org/10.1007/11847250_9.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Fürer, Martin, Serge Gaspers, and Shiva Prasad Kasiviswanathan. "An Exponential Time 2-Approximation Algorithm for Bandwidth." In Parameterized and Exact Computation. Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-11269-0_14.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Chitnis, Rajesh, MohammadTaghi Hajiaghayi, and Guy Kortsarz. "Fixed-Parameter and Approximation Algorithms: A New Look." In Parameterized and Exact Computation. Springer International Publishing, 2013. http://dx.doi.org/10.1007/978-3-319-03898-8_11.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Adiga, Abhijin, Jasine Babu, and L. Sunil Chandran. "Polynomial Time and Parameterized Approximation Algorithms for Boxicity." In Parameterized and Exact Computation. Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-33293-7_14.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Fellows, Michael R., Ariel Kulik, Frances Rosamond, and Hadas Shachnai. "Parameterized Approximation via Fidelity Preserving Transformations." In Automata, Languages, and Programming. Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-31594-7_30.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Parameterized approximation"

1

Lokshtanov, Daniel, Saket Saurabh, and Vaishali Surianarayanan. "A Parameterized Approximation Scheme for Min -Cut." In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2020. http://dx.doi.org/10.1109/focs46700.2020.00079.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Jansen, Klaus. "Parameterized Approximation Scheme for the Multiple Knapsack Problem." In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2009. http://dx.doi.org/10.1137/1.9781611973068.73.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Hartung, Sepp, and Andre Nichterlein. "On the Parameterized and Approximation Hardness of Metric Dimension." In 2013 IEEE Conference on Computational Complexity (CCC). IEEE, 2013. http://dx.doi.org/10.1109/ccc.2013.36.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Hengfei Zhang, Yong Yan, Guang Yang, and Xiaojun Tan. "Multi-Approximation based Time-Parameterized moving objects R-tree." In 2013 15th IEEE International Conference on Communication Technology (ICCT). IEEE, 2013. http://dx.doi.org/10.1109/icct.2013.6820471.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Aras, A. C., O. Kaynak, and I. Batyrshin. "Nonlinear function approximation based on fuzzy algorithms with parameterized conjunctors." In 2013 IEEE International Conference on Mechatronics (ICM). IEEE, 2013. http://dx.doi.org/10.1109/icmech.2013.6518515.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Saleh, Khaled, Vikrant Aute, and Kurt Reinhard Radermacher. "Heat Exchanger Optimization Using Approximation and Parallel Parameterized CFD (PPCFD)." In SAE 2013 World Congress & Exhibition. SAE International, 2013. http://dx.doi.org/10.4271/2013-01-1163.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Shukla, Amit. "Control Bifurcations of a Magneto-Rheological Fluid Based Active Suspension System." In ASME 2005 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. ASMEDC, 2005. http://dx.doi.org/10.1115/detc2005-85436.

Full text
Abstract:
Design of active suspension systems is well known, however the notion of control bifurcations for the design of such systems has been introduced recently. A nonlinear active suspension system consisting of a magneto-rheological damper is analyzed in this work. It is well known that a parameterized nonlinear differential equation can have multiple equilibria as the parameter is varied. A local bifurcation of a parameterized nonlinear system typically happens because some eigenvalues of the parameterized linear approximating differential equation cross the imaginary axis and there is a change in
APA, Harvard, Vancouver, ISO, and other styles
8

Zhao, Haifeng, and Gregory J. Rodin. "Multiscale Modeling of Random Lattices: Critical Issues on Continuum Approximation." In ASME 2011 International Mechanical Engineering Congress and Exposition. ASMEDC, 2011. http://dx.doi.org/10.1115/imece2011-65783.

Full text
Abstract:
In this work, we are concerned that transmission of various boundary conditions through irregular lattices. The boundary conditions are parameterized using trigonometric Fourier series, and it is shown that, under certain conditions, transmission through irregular lattices can be well approximated by that through classical continuum. It is determined that such transmission must involve the wavelength of at least 12 lattice spacings; for smaller wavelength classical continuum approximations become increasingly inaccurate.
APA, Harvard, Vancouver, ISO, and other styles
9

Ninomiya, Hiroshi. "Parameterized online quasi-Newton training for high-nonlinearity function approximation using multilayer neural networks." In 2011 International Joint Conference on Neural Networks (IJCNN 2011 - San Jose). IEEE, 2011. http://dx.doi.org/10.1109/ijcnn.2011.6033583.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Onus, Melih, and Andréa W. Richa. "Parameterized Maximum and Average Degree Approximation in Topic-Based Publish-Subscribe Overlay Network Design." In 2010 IEEE 30th International Conference on Distributed Computing Systems. IEEE, 2010. http://dx.doi.org/10.1109/icdcs.2010.54.

Full text
APA, Harvard, Vancouver, ISO, and other styles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography