|
Cristina Bazgan
Cristina Bazgan is a French computer scientist who studies combinatorial optimization and graph theory problems from the points of view of parameterized complexity, fine-grained complexity, approximation algorithms, and regret. Bazgan earned her Ph.D. in 1998 from the University of Paris-Sud. Her dissertation, ''Approximation de problèmes d'optimisation et de fonctions totales de NP'', was supervised by Miklos Santha. She is a professor at Paris Dauphine University, associated with Lamsade, the Laboratory for Analysis and Modeling Systems for Decision Support. Bazgan became a junior member of the Institut Universitaire de France The Institut Universitaire de France (IUF, Academic Institute of France), is a service of the French Ministry of Higher Education that annually distinguishes a small number of university professors for their research excellence, as evidenced by t ... in 2011. References External linksHome page French women computer scientists Theoretical comp ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Combinatorial Optimization
Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combinatorial optimization problems are the travelling salesman problem ("TSP"), the minimum spanning tree problem ("MST"), and the knapsack problem. In many such problems, such as the ones previously mentioned, exhaustive search is not tractable, and so specialized algorithms that quickly rule out large parts of the search space or approximation algorithms must be resorted to instead. Combinatorial optimization is related to operations research, algorithm theory, and computational complexity theory. It has important applications in several fields, including artificial intelligence, machine learning, auction theory, software engineering, VLSI, applied mathematics and theoretical computer science. Applications Basic applications of combina ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph theory), vertices'' (also called ''nodes'' or ''points'') which are connected by ''Glossary of graph theory terms#edge, edges'' (also called ''arcs'', ''links'' or ''lines''). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics. Definitions Definitions in graph theory vary. The following are some of the more basic ways of defining graphs and related mathematical structures. Graph In one restricted but very common sense of the term, a graph is an ordered pair G=(V,E) comprising: * V, a Set (mathematics), set of vertices (also called nodes or points); * ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Parameterized Complexity
In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. The complexity of a problem is then measured as a function of those parameters. This allows the classification of NP-hard problems on a finer scale than in the classical setting, where the complexity of a problem is only measured as a function of the number of bits in the input. This appears to have been first demonstrated in . The first systematic work on parameterized complexity was done by . Under the assumption that P ≠ NP, there exist many natural problems that require super-polynomial running time when complexity is measured in terms of the input size only but that are computable in a time that is polynomial in the input size and exponential or worse in a parameter . Hence, if is fixed at a small value and the growth ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Fine-grained Reduction
In computational complexity theory, a fine-grained reduction is a transformation from one computational problem to another, used to relate the difficulty of improving the time bounds for the two problems. Intuitively, it provides a method for solving one problem efficiently by using the solution to the other problem as a subroutine. If problem A can be solved in time a(n) and problem B can be solved in time b(n), then the existence of an (a,b)-reduction from problem A to problem B implies that any significant speedup for problem B would also lead to a speedup for problem A. Definition Let A and B be computational problems, specified as the desired output for each possible input. Let a and b both be time-constructible functions that take an integer argument n and produce an integer result. Usually, a and b are the time bounds for known or naive algorithms for the two problems, and often they are monomials such as n^2. Then A is said to be (a,b)-reducible to B if, for every real numb ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Approximation Algorithm
In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solution to the optimal one. Approximation algorithms naturally arise in the field of theoretical computer science as a consequence of the widely believed P ≠ NP conjecture. Under this conjecture, a wide class of optimization problems cannot be solved exactly in polynomial time. The field of approximation algorithms, therefore, tries to understand how closely it is possible to approximate optimal solutions to such problems in polynomial time. In an overwhelming majority of the cases, the guarantee of such algorithms is a multiplicative one expressed as an approximation ratio or approximation factor i.e., the optimal solution is always guaranteed to be within a (predetermined) multiplicative factor of the returned solution. However, there a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Regret (decision Theory)
In decision theory, regret aversion (or anticipated regret) describes how the human emotional response of regret can influence decision-making under uncertainty. When individuals make choices without complete information, they often experience regret if they later discover that a different choice would have produced a better outcome. This regret can be quantified as the difference in value between the actual decision made and what would have been the optimal decision in hindsight. Unlike traditional models that consider regret as merely a post-decision emotional response, the theory of regret aversion proposes that decision-makers actively anticipate potential future regret and incorporate this anticipation into their current decision-making process. This anticipation can lead individuals to make choices specifically designed to minimize the possibility of experiencing regret later, even if those choices are not optimal from a purely probabilistic expected-value perspective. Regre ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
University Of Paris-Sud
Paris-Sud University (), also known as the University of Paris — XI (or as the Orsay Faculty of Sciences, University of Paris before 1971), was a French research university distributed among several campuses in the southern suburbs of Paris, including Orsay, Cachan, Châtenay-Malabry, Sceaux, Hauts-de-Seine, Sceaux, and Kremlin-Bicêtre campuses. In 2019, the university was replaced by the Paris-Saclay University. History Paris-Sud, as the Orsay Faculty of Sciences, was originally part of the University of Paris, which was subsequently split into several universities. After World War II, the rapid growth of nuclear physics and chemistry meant that research needed more and more powerful accelerators, which required large areas. The University of Paris, the and the looked for space in the south of Paris near Orsay. Later some of the teaching activity of the Faculty of Sciences in Paris was transferred to Orsay in 1956 at the request of Irène Joliot-Curie and Frédéric Joli ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Paris Dauphine University
Paris Dauphine University - PSL () is a Grande École and public institution of higher education and research based in Paris, France, Collegiate university, constituent college of PSL University. As of 2022, Dauphine has 9,400 students in 8 fields of study (law, economics, finance, computer science, journalism, management, mathematics, social sciences), plus 3,800 in executive education. Its status as a , adopted in 2004, allows it to select its students. On average, 90 to 95% of accepted students received either high distinctions or the highest distinctions at their French High School National Exam results (Examen National du Baccalauréat). Dauphine is also a member of the Conférence des Grandes écoles, Conférence des Grandes Écoles. Research at Dauphine concerns "organization and decision sciences", organized in 6 research laboratories (5 of which are mixed units also staffed by French National Centre for Scientific Research, CNRS researchers): the ''CEREMADE'' Center for Re ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Institut Universitaire De France
The Institut Universitaire de France (IUF, Academic Institute of France), is a service of the French Ministry of Higher Education that annually distinguishes a small number of university professors for their research excellence, as evidenced by their international recognition. Only around 2% of French university faculty are members (active or honorary) of the IUF. Organization The Institute was created by decree on 26 August 1991. At least two-thirds of IUF members belong to universities outside Paris. The purpose of the IUF is to encourage the development of high-level, interdisciplinary research in universities. It has three primary objectives: # To encourage institutions and research professors to achieve excellence in research, creating positive impacts on teaching, the training of young researchers and the dissemination of knowledge; # Contribute to the feminization of the research sector; # Foster a balanced distribution of university research across the country, and thus s ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
French Women Computer Scientists
French may refer to: * Something of, from, or related to France ** French language, which originated in France ** French people, a nation and ethnic group ** French cuisine, cooking traditions and practices Arts and media * The French (band), a British rock band * "French" (episode), a live-action episode of ''The Super Mario Bros. Super Show!'' * ''Française'' (film), a 2008 film * French Stewart (born 1964), American actor Other uses * French (surname), a surname (including a list of people with the name) * French (tunic), a type of military jacket or tunic * French's, an American brand of mustard condiment * French (catheter scale), a unit of measurement * French Defence, a chess opening * French kiss, a type of kiss See also * France (other) * Franch, a surname * French Revolution (other) * French River (other), several rivers and other places * Frenching (other) * Justice French (other) Justice French may refer to: * C. G ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Theoretical Computer Scientists
A theory is a systematic and rational form of abstract thinking about a phenomenon, or the conclusions derived from such thinking. It involves contemplative and logical reasoning, often supported by processes such as observation, experimentation, and research. Theories can be scientific, falling within the realm of empirical and testable knowledge, or they may belong to non-scientific disciplines, such as philosophy, art, or sociology. In some cases, theories may exist independently of any formal discipline. In modern science, the term "theory" refers to Scientific theory, scientific theories, a well-confirmed type of explanation of nature, made in a way Consistency, consistent with the scientific method, and fulfilling the Scientific theory#Characteristics of theories, criteria required by modern science. Such theories are described in such a way that scientific tests should be able to provide Empirical evidence, empirical support for it, or Empirical evidence, empirical contradi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
