text:
# Everyone knows bullets are magnetically pulled to anyone who's about to retire

Decided to try a little writing with this puzzle, so forgive the bit of extra length. Hopefully the story is entertaining enough to forgive a tiny bit of extra length ;)

"Alex is almost three, and his little brother there is two." Chris explained, as the squad-mates made appropriate comments about how adorable the photo of Chris' wife and two children was.

"Linda hated me accepting this tour, she keeps telling me I better take care of myself so I can be there when Alex graduates. I've missed her and the kids so much lately; I'm thinking when I get home next month I'll tell her she's won and I'll find another job. I'm not sure what I could do, been a military brat as long as I can remember, but I guess I could be a police officer or something. It would be nice to actually get to see the kids every day. Linda's been wanting another child, I wouldn't mind a little girl..."

Chris' planning was interrupted by the sound of an explosion nearby. An ambush! The little squad of five saw over a dozen men coming out of hiding, they were seriously outnumbered! Chris ran to grab a rifle and return fire, but never made it before collapsing in pain from a belly shot. The squad managed to kill two of their attackers before the last man fell. Five casualties to two, for all their training they hadn't even manage to return half the damage inflicted on them, an inglorious battle in the end, cursed ambushes! Chris' last thought before everything went black was of little Alex and that graduation Linda had wanted them to attend together.

Linda had always feared the day would come when a solemn soldier knocked on her door instead of Chris. The soldier was dignified and sympathetic, offering his condolences and best wishes, but that didn't make it any better. They wouldn't even tell Linda exactly how it happened, they had to protect "military intelligence" apparently. No just some fancy terms like "enemy action" and "regrettable casualties". Not that it really mattered, what mattered was someone had shot Chris and all the fellow soldiers Chris had cared for, and no man had survived the attack. Linda didn't know what to do, how would she explain this to the kids?

Time went by, and the little family kept living after the tragedy. The memory of the visit of a soldier in the night never left Linda, though it got easier with time. The widow never got over her love for Chris, never remarrying again or even even dating again. Alex and his brother Josh grew up without a father to love or care for them, the children were so young they didn't even remember what it had been like to have a father, but still they grew...

Almost 20 years Later Lisa stood in the college auditorium, filled with soon to be graduates. Alex stood at the front of them all, giving the valedictorian speech. He told the graduates of the father he couldn't remember that died when he was a child, and shared the story of Chris' last battle, telling the listeners how life may never go as planned. But he ended his story with a message of hope and perseverance and the ability to survive and grow with whatever hardship life throws at you.

After the ceremony Linda hugged her son, telling him how proud she was. Lisa, Alex's little sister, seemed more interested in listening to her music and checking out the college she was planning to be attending soon then Alex or his speech, but she still gave him the obligatory congratulations.

"Well, Lisa may be too busy plotting to take over this place once you leave to have listened, but I'll say I was impressed with that speech. But I think you gave me way to much credit" said Chris. Not that Chris minded too much, after all how could a parent be upset on the day of their child's graduation? This was a date Chris had been promising Linda to attend for two decades, and it was worth the wait.

Whats happening here, has the ghost of Alex's dead dad stopped in to visit? A good answer should take the time to explain all the apparent discrepancies they can.

Hints to narrow down possible answers are below.

• There are not two Chrises, There is only one person with each name in the story

• The military did not make a mistake (other then falling for an ambush I suppose), they provided accurate information

• The ambush was real, no military exercise, dreams, or other simulations.

• Chris was not brought back from the dead, no ghosts, clones, or undead vampires either.

• Seems to me Chris didn't die Aug 12, 2016 at 19:32
• Did Josh turn into Lisa, or was there a third child? Aug 12, 2016 at 19:49
• Lisa's been wanting another child. But Lisa is said to be Alex's little sister, who doesn't appear to exist at the beginning of the story... Aug 12, 2016 at 19:52
• Seems to me, too, that Chris didn't die -- if he had, nobody would ever have known of his "last thought before everything went black". But what widower? Aug 12, 2016 at 20:43
• "The widower never got over her love..." Widowers are male by definition. Is this intentional, or did you mean "widow"? Also, I think "even even dating again" is a typo where one should be "ever". Aug 12, 2016 at 22:35

The story

never says Chris died, just that (s)he took a belly shot, fell and his wife was visited by a soldier to explain something happened in which no man survived.

So my guess is

Chris is a women and did survive.

Definition:

casualty is "a member of the armed forces lost to service through death, wounds, sickness, capture, or because his or her whereabouts or condition cannot be determined."

Further:

@Morgan G not remembering a father wouldn't be an obstacle if they had two mothers. Still have a father (biological) but they never knew/remember him. @Daphne as far as explaining it to the kids maybe Chris is paralyzed, disfigured, etc. there are many things that can be difficult to explain.

• That was my thought too but I couldn't think of a way to explain "they didn't even remember what it had been like to have a father" Aug 12, 2016 at 19:38
• The discussion of the casualties rules this out. Their squad was 5. The casualty count was 5 to 2, and their squad did not deal half the casualties they sustained. That means they sustained the larger amount of casualties, thus their whole squad died. Aug 12, 2016 at 19:46
• Added a definition of casualty to the answer. Aug 12, 2016 at 20:00
• Easy way to resolve the "no father" bit: there was a father, unnamed throughout the story, who happened to die when the children were young. (Alternatively, not remembering something that didn't happen is pretty common.) Linda was wondering about how to explain to the kids that their other mother was currently a POW, or would be unable to bear further children (as planned) due to injuries sustained in the ambush.
– user28820
Aug 12, 2016 at 21:53
• @jpmc26 I would guess the Lisa/Linda and widower/widow things are typos, with 5/6 of his latest questions on hold or closed the OP doesn't exactly have a hot streak with regards to well articulated questions (sorry OP). Aug 12, 2016 at 23:19

Chris is at Alex's graduation because

She's a woman, and was a casualty of the combat that did not die.

Chris and Linda are

Not married, Linda was married to someone else in the squad, and Chris and Linda have some other type of personal relationship, likely familial.

Lisa is

A young child of Linda's, that wants a little sister at the beginning, apparently having only brothers.

Chris's children

Are never named, but they are in the photos with at least Alex and Josh, and Chris' wife. They

I still can't explain

Who the 'widower' is, perhaps 'widow' was meant? But I can't just dismiss it...

My guess is that

Lisa is trans and was Josh. Why? As has been explained in other answers, everyone in the squad died, so Chris died, so there was no opportunity for Chris and Linda to have a third child. The words "what it had been like to have a father" indicate that the two children had known their father, thus suggesting that they were not brought up by two women. What is telling for me, though, is that the last mention of Josh comes before the first mention of Lisa, suggesting that they are one and the same.


text:
## Error message

• Notice: Undefined property: views_plugin_style_default::$date_info in include() (line 31 of /home/it/www/www-icts/sites/all/themes/riley/templates/date-views-pager--calendar.tpl.php). • Notice: Trying to get property of non-object in include() (line 31 of /home/it/www/www-icts/sites/all/themes/riley/templates/date-views-pager--calendar.tpl.php). • Notice: Undefined property: views_plugin_style_default::$date_info in include() (line 32 of /home/it/www/www-icts/sites/all/themes/riley/templates/date-views-pager--calendar.tpl.php).
• Notice: Trying to get property of non-object in include() (line 32 of /home/it/www/www-icts/sites/all/themes/riley/templates/date-views-pager--calendar.tpl.php).
• Notice: Undefined property: views_plugin_style_default::\$date_info in include() (line 34 of /home/it/www/www-icts/sites/all/themes/riley/templates/date-views-pager--calendar.tpl.php).
• Notice: Trying to get property of non-object in include() (line 34 of /home/it/www/www-icts/sites/all/themes/riley/templates/date-views-pager--calendar.tpl.php).
Monday, January 21, 2019
Programs
03 January 2019 to 25 January 2019
Ramanujan Lecture Hall, ICTS Bangalore
The great observational progress in cosmology has revealed some very intriguing puzzles, the most important of which are the existence of new mysterious components of the Universe: the dark matter...more
Lectures
21 January 2019 to 24 January 2019
Emmy Noether Seminar Room, ICTS Bangalore
Lecture 1: Jan 21, 2019 at 11:00 am Lecture 2: Jan 23, 2019 at 11:00 am Lecture 3: Jan 24, 2019 at 11:00 am Abstract: Entanglement entropy in quantum field theories suffers from UV divergences, and...more

format: plain


text:
# How do you find the slope and intercept of 8x-1/2y=-2?

Sep 11, 2016

$8 x - \frac{1}{2} y = - 2$

Solve for y

$- \frac{1}{2} y = - 8 x - 2$

$y = 16 x + 4$

Slope-intercept form: $y = m x + b$, m=slope, b=y-intercept

Slope=16, y-intercept=$\left(0 , 4\right)$

x-intercept: let y=0

$0 = 16 x + 4$

$- 4 = 16 x$

$- \frac{1}{4} = x$

x-intercept= $\left(- \frac{1}{4} , 0\right)$


text:
mersenneforum.org Polynomial Problem
 Register FAQ Search Today's Posts Mark Forums Read

 2016-07-28, 02:12 #1 jvang veganjoy     "Joey" Nov 2015 Middle of Nowhere,AR 3·5·29 Posts Polynomial Problem I'm in an Algebra II class, and the current topic is polynomials. I was working on a problem, but I have no idea where to begin. Suppose $$f$$ is a polynomial such that $$f(0)=47, f(1)=32, f(2)=-13,$$ and $$f(3)=16.$$ What is the sum of the coefficients of $$f$$? Clearly, to find the sum of the coefficients, I need to find the function $$f$$. I'm not sure how to find $$f$$ given a set of points. One potential option I saw on the Internet was polynomial interpolation, but the Wikipedia article was very complicated. Is there a simpler explanation of this technique, if it is the right approach? If not, what is the right approach to this problem? Thanks!
 2016-07-28, 04:14 #2 jwaltos     Apr 2012 36410 Posts f(x)=a*x^4+b*x^3+c*x^2+d*x+47, since there are 4 roots assuming a single variable. Substitute the root given for x in four separate equations then solve for the coefficients. Check all roots via substitution once the function is obtained then sum your coefficients. This is how I would start. Last fiddled with by jwaltos on 2016-07-28 at 04:21
2016-07-28, 04:21   #3
axn

Jun 2003

2×32×269 Posts

Quote:
 Originally Posted by jwaltos f(x)=a*x^4+b*x^3+c*x^2+d*x+47, since there are 4 roots assuming a single variable.
Off by 1, I think.

2016-07-28, 04:24   #4
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

17×271 Posts

Quote:
 Originally Posted by jwaltos f(x)=a*x^4+b*x^3+c*x^2+d*x+47, since there are 4 roots assuming a single variable. This is how I would start.
Why are there four roots? I see evidence for two. With 4 ordered pairs given, create a polynomial with four unknown coefficients, including the constant term. Since f(0) = 47, 47 is the constant term. That leaves three unknown coeffs in a cubic (degree 3).

 2016-07-28, 04:24 #5 jwaltos     Apr 2012 22×7×13 Posts Probably, Jack Daniels, Jim Beam and Johnny Walker were all giving advice.
 2016-07-28, 04:43 #6 Antonio     "Antonio Key" Sep 2011 UK 32×59 Posts Surely f(1) = 32 = the sum of the coefficients of f(x) for a polynomial of any degree, as all xn = 1 so we are reduced to an*1 + an-1*1 + an-2*1 + ........ + a0 = 32
2016-07-28, 05:27   #7
axn

Jun 2003

2·32·269 Posts

Quote:
 Originally Posted by Antonio Surely f(1) = 32 = the sum of the coefficients of f(x) for a polynomial of any degree, as all xn = 1 so we are reduced to an*1 + an-1*1 + an-2*1 + ........ + a0 = 32

 2016-07-28, 13:44 #8 jvang veganjoy     "Joey" Nov 2015 Middle of Nowhere,AR 3·5·29 Posts I think I get the idea. So the polynomial must be of the form $$ax^3+bx^2+cx+d,$$ since there are 4 given points, and one of them is the $$y$$ intercept. So if $$x=1,$$ all of the $$x$$ values stay the same since $$1$$ to any power is $$1$$. However, if $$f(1)=32,$$ then that is $$a+b+c+47,$$ so I would need to subtract $$47$$ from $$a+b+c$$ to get $$-7$$ as the answer. Either that or I overthought this problem. Last fiddled with by jvang on 2016-07-28 at 13:47
 2016-07-28, 17:08 #9 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 7×911 Posts Whatever the polynomial, f(1) is the sum of its coefficients. You weren't given the degree of the polynomial, because you don't need it. (because if f(x) = sum a_i x^i, then f(1) = sum a_i because all the powers of 1 are 1) Equally f(-1) is the alternating sum of its coefficients, so f(-1)+f(1)/2 is the sum of the even-numbered coefficients. This turns into a root into Fourier analysis: think about $f(\omega)$ where $\omega$ is a root of unity. Last fiddled with by fivemack on 2016-07-28 at 17:09
 2016-07-29, 03:35 #10 LaurV Romulan Interpreter     Jun 2011 Thailand 3×11×277 Posts @OP: Are you sure the problem asks for the coefficient's sum? As the problem is given, it is either tricky (because you only need to know f(1) and nothing else, no information about the degree is necessary, and the other 3 values given are futile) or either it wanted to ask for the sum of the roots. In this case, you need all 4 values, make s system with 4 equations and 4 variables, check if they are not linear (i.e. the system may not be independent, in such case a lower-degree poly will fit) and/or use Vieta's formulas to get the sum. Last fiddled with by LaurV on 2016-07-29 at 03:36 Reason: link
2016-07-29, 14:46   #11
CRGreathouse

Aug 2006

10111010010012 Posts

Quote:
 Originally Posted by LaurV @OP: Are you sure the problem asks for the coefficient's sum?
I'm pretty sure that's what it's asking. Otherwise, how do you know it's a quartic f(x) and not a quintic, say f(x) * (x - 7)?

 Similar Threads Thread Thread Starter Forum Replies Last Post Max0526 NFS@Home 9 2017-05-20 08:57 carpetpool Miscellaneous Math 14 2017-02-18 19:46 carpetpool carpetpool 4 2017-02-03 12:48 firejuggler Aliquot Sequences 7 2010-05-29 02:46 R.D. Silverman NFSNET Discussion 13 2005-09-16 20:07

All times are UTC. The time now is 16:03.

Mon Jan 18 16:03:54 UTC 2021 up 46 days, 12:15, 0 users, load averages: 1.19, 1.51, 1.61


text:
# $PT$-symmetric invisible defects and confluent Darboux-Crum transformations

@article{Correa2015PTsymmetricID,
title={\$PT\$-symmetric invisible defects and confluent Darboux-Crum transformations},
author={Francisco Correa and V{\'i}t Jakubsk{\'y} and Mikhail S. Plyushchay},
journal={Physical Review A},
year={2015},
volume={92},
pages={023839}
}
• Published 2 June 2015
• Mathematics
• Physical Review A
We show that confluent Darboux-Crum transformations with emergent Jordan states are an effective tool for the design of optical systems governed by the Helmholtz equation under the paraxial approximation. The construction of generic, asymptotically real and periodic, $PT$-symmetric systems with local complex periodicity defects is discussed in detail. We show how the decay rate of the defect is related with the energy of the bound state trapped by the defect. In particular, the bound states in…
48 Citations

## Figures from this paper

• Physics
Physical Review A
• 2019
We present a framework for the construction of solvable models of optical settings with genuinely two-dimensional landscapes of refractive index. The solutions of the associated non-separable Maxwell
Hidden symmetries of non-relativistic so(2, 1) ∼= sl(2,R) invariant systems in a cosmic string background are studied using the conformal bridge transformation. Geometric properties of this
• Physics
• 2022
: Supersymmetric extensions of the 1D and 2D Swanson models are investigated by applying the conformal bridge transformation (CBT) to the ﬁrst order Berry-Keating Hamiltonian multiplied by i and its
• Physics
• 2021
Supersymmetric extensions of the 1D and 2D Swanson models are investigated by using the conformal bridge transformation. The latter plays the role of the Dyson map that transforms the models into
• Physics
Journal of High Energy Physics
• 2022
Supersymmetric extensions of the 1D and 2D Swanson models are investigated by applying the conformal bridge transformation (CBT) to the first order Berry-Keating Hamiltonian multiplied by i and its
• Mathematics
Physical Review D
• 2019
The Klein four-group symmetry of the eigenvalue problem equation for the conformal mechanics model of de Alfaro-Fubini-Furlan (AFF) with coupling constant $g=\nu(\nu+1)\geq -1/4$ undergoes a complete
• Physics
Optics letters
• 2018
All BICs found here are the most rapidly growing modes; therefore, they can be excited from noisy inputs and, importantly, should dominate the beam dynamics in experiments.
A key feature of integrable systems is that they can be solved to obtain exact analytical solutions. In this thesis we show how new models can be found through generalisations of some well known
• F. Correa
• Mathematics
Physics of Particles and Nuclei Letters
• 2017
We describe how Darboux–Crum transformations with Jordan states provide an useful method for the design of complex optical systems. We focus in the construction of PT-symmetric models with features

## References

SHOWING 1-10 OF 138 REFERENCES

• Physics
• 2014
By applying Darboux--Crum transformations to the quantum one-gap Lam\'e system, we introduce an arbitrary countable number of bound states into forbidden bands. The perturbed potentials are
• Physics, Mathematics
• 2014
We consider the two most general families of the (1+1)D Dirac systems with transparent scalar potentials, and two related families of the paired reflectionless Schrodinger operators. The ordinary N=2
• Physics
• 2011
Some time ago, Thies et al. showed that the Gross-Neveu model with a bare mass term possesses a kink-antikink crystalline phase. Corresponding self-consistent solutions, known earlier in polymer
• Physics
• 2009
The Helmholtz equation can be reshaped into a form analogous to the Schrödinger equation with the term labeled ‘the optical potential’. By following this analogy, we conclude that there exist certain
• Mathematics, Physics
• 2012
The origin of spectral singularities in finite-gap singly periodic $\mathcal{P}\mathcal{T}$-symmetric quantum systems is investigated. We show that they emerge from a limit of band-edge states in a
This Letter shows that bound states in the continuum (BIC), which are normalizable modes with energy embedded in the continuous spectrum of scattered states, exist in certain optical waveguide
• Physics
• 2011
The PT-symmetric potential V{sub 0}[cos(2{pi}x/a)+i{lambda}sin(2{pi}x/a)] has a completely real spectrum for {lambda}{ 1. At the symmetry-breaking threshold {lambda}=1 some of the eigenvectors become
• Physics
• 2013
We show that the formalism of supersymmetry (SUSY), when applied to parity-time (PT) symmetric optical potentials, can give rise to novel refractive index landscapes with altogether non-trivial
• Physics
• 2010
The basic properties of Floquet-Bloch (FB) modes in parity-time (PT)-symmetric optical lattices are examined in detail. Due to the parity-time symmetry of such complex periodic potentials, the


text:
# Tag Info

## Hot answers tagged traveling-salesman

18

If you are interested in solving the TSP, the Concorde TSP solver is a very powerful and easy-to-use tool. I do not know what the licensing options are for commercial applications, but for research purposes it is free and easy to use (if you are familiar with C/C++)

17

Search for orienteering problem or prize-collecting TSP.

16

If you cannot use Concorde as suggested by Albert, I'd suggest you look for an implementation of the Lin-Kerninghan-Heuristic (which is also included in Concorde). It iterates between 2-opt and 3-opt to find a good solution quickly. If you are interested in the best solution or need to know a bound on the best possible solution, then Concorde is the way to ...

13

The answer to this question is quite complicated. There are two main types of vehicle routing problems, the offline and the online problem. Solving the offline problem takes longer and is used to make planning-level decisions. The online problem is solved as real-time information comes in, and tells us what to do at the low level (as in which vehicle should ...

13

There is a paper of Ahammed and Moscato on finding hard instances for Concorde using Lindenmeyer systems. They were able to find small instances with about 1500 cities that took (in 2011) more than 4 hours to solve. One should probably add that "hard" always means "hard for some algorithm". So, for balance, here is a paper of Kate Smith-Miles & van ...

12

This has to depend on instance size. For a sports scheduling problem I worked on, it definitely made life easier to simply put in all the $|S| \le 3$ constraints (not exactly subtour, but very similar). But $n=30$ in that case. If you want to solve TSPs with, say, 1000 nodes, then $n^3$ is pretty big, and most of them are completely irrelevant. You will ...

11

This paper by Pisinger and Ropke is particularly useful when working on (A)LNS, and provides great guidance and an overview of operators/neighborhoods. I would suggest this paper by Vidal et al. for more genetic search inspired aspects.

11

Why would people spend time improving MTZ, if DFJ is much tighter and all compact MTZ improvements never come close to DFJ? Although this might not be used in TSP solvers, it could still be interesting to research finding tight compact formulations for the TSP from a theoretical perspective. In the paper by H. Sherali and P. Driscoll, the authors ...

11

There are a few problems in this category. They are variants of the Travelling Salesman Problem in which you don't need to visit all customers, but can choose which ones to visit. They fall under the general name of Travelling Salesman Problems with Profits. The main variants are: The Orienteering Problem (OP) in which you want to maximise the profit ...

10

This recent review on rich routing problems may be helpful: http://repository.psau.edu.sa/jspui/retrieve/6358c84c-e14d-4e4c-8645-c8f7320606ab/EJOR_2015.pdf A quick scan on the categories would suggest you have: 1.3.2 Multiple Depots 2.1.1.2 Heterogeneous Vehicles 2.2.1 Restrictions on Customer Waiting Time 2.2.2 Restrictions on Road Access 2.4 ...

9

You can model your problem by defining separate variables for each traveling salesman. Below I will use 'vehicle' instead of 'traveling salesman', which is more common in this setting. Defining separate variables Let $n$ be the number of customers and let $m \le n$ be the number of vehicles. For each vehicle $k = 1, \dots, m$, define the variables $$x_{ij}^k ... 9 Thanks to @Laurent Perron for their answer - I've tried modifying the code as follows, and it appears to work fine: from __future__ import print_function from ortools.constraint_solver import routing_enums_pb2 from ortools.constraint_solver import pywrapcp def create_data_model(): """Stores the data for the problem.""" data = {} data['... 8 These common neighborhoods for TSP/VRP might be useful: 2-opt, 3-opt, ..., k-opt change 1 visit: remove 1 visit from a chain and insert it somewhere else in a chain swap 2 visits change a subchain of visits: remove a number of sequential visits from a chain and insert it somewhere else in a chain, sometimes reversed swap 2 subchains ruin&recreate 8 To my knowledge, there is yet no known constant worst-case error bound \eta for farthest insertion nor a proof that no constant bound exists. The results you mention here require symmetric TSP instances with costs that satisfy the triangle inequality, if I am not mistaken. Nearest and cheapest insertion benefit from the fact that it can be shown that ... 8 You could also give a try to VROOM, which can be used for commercial use. It can solve TSP and some variants of the VRP such as VRPTW and CVRP. Here is the API documentation : https://github.com/VROOM-Project/vroom/blob/master/docs/API.md What you can is to start with the demo server to see if it can fit on small instances and then install it to use it as ... 8 Y. Kaempfer and L. Wolf, in their recent paper [1] applied ML techniques to solve the Multiple Traveling Salesmen Problem (mTSP). They provide a mathematical model for problem formulation which can be modified to cover what you need in the solution to your problem. You can replace the constraint (2d) which is:$$\forall 2\leq j \leq n: \sum\limits_{i=1}^{n}...

8

There is a paper by Papadimitriou and Steiglitz here to construct instances, which are very hard for local searches to find optimal solution.

8

As Marco briefly explained in his comment, TSP is not the ideal problem to teach the column generation approach. TSP is suited for the row generation approach, also known as branch-and-cut, by following the Dantzig–Fulkerson–Johnson formulation that you can easily find on the web (for example, on the Wikipedia page related to TSP). On the other, VRP is a ...

8

I think one of the reasons you have difficulties implementing the constraint is because it is not written correctly. You need to be more precise with your indexes. If $N:=\{1,...,n \}$, you can write the constraint as follows: $$\sum_{i \in S}\sum_{j \in S, j\neq i} x_{ij} \le |S| -1 \quad \forall S \subset N, 2 \le |S| \le n-1$$ This means that you have ...

7

I went over all the math included in the proof and confirmed that your claim which is: $$\frac{3a}2+2b+\sqrt{2(n-2)ab}\le\sqrt{2(n-1)ab}+2(a+b)$$ is true. But I think they didn't use the tighter bound to make the lemma more general. In the bound that you proposed the following assumption for the number of nodes must be true: $$|X|\ge 2$$ But in the ...

7

I am a researcher in vehicle routing, and my answer is based on my experience as a researcher, conversations with practitioners and consultants, and seminars and conference talks I have attended. You make a very interesting observation: solving VRP's to optimality is currently only possible for hundreds of customers, while problems in practice are ...

7

As suggested by Larry Snyder in the comments to your question, you can reduce your problem to a standard traveling salesman problem by means of precomputing the distances. In particular, consider the complete graph with nodes given by $S$. Moreover, consider as distance between nodes $s_1$ and $s_2$ the shortest path between those nodes in your original ...

7

If the distance between your nodes follows the triangle inequality (you can never travel faster between two points by adding an intermediary step), then the shortest path visits each node only once. However, if your network has nodes $a$, $b$, $c$ such that $$d(a,b) \geq d(a,c) + d(c,b)$$ any path that goes from $a$ to $b$ will always go through. So you can ...

6

Stating the obvious, even if you don't have a depot in its traditional definition, you can still use dummy nodes as your depot(s). I think an area closer to what you are looking for can be Ambulance dispatching. It has a richer literature compared to other roadside assistance type VRP. Moreover, during disasters, the roads can be blocked or very hard to ...

6

As @OguzToragay has mentioned, writing $\sqrt{2(n-1)ab}$ instead of $\sqrt{2(n-2)ab}$ allows for the trivial case of one point in the Euclidean plane since $|X|\ge1$ in section 2. The other point to make is that writing $2(a+b)$ instead of $3a/2+2b$ means that $T^*(X)$ can be succinctly expressed in terms of the perimeter of a rectangle, as in the case in ...

6

You can create three nodes for one city. In other words, You create a bus station, train station, airport in one city. If you arrive in city A with a train but leave with a plane, you have to move from the train station to Airport. And then you can assign 0 (or appropriate quantities, emission or time) for moving between any of them within the same city. ...

6

These CH work: Nearest Neighbor First Fit, First Fit Decreasing, Strongest Fit, Strongest Fit Decreasing Cheapest Insertion, Regret Insertion Christofides algorithm (doesn't really deal well with extra constraints) Clarke-Wright algorithm (more for vanilla VRP, doesn't really deal well with extra constraints) Cook's book "In Pursuit of the Traveling ...

6

There are some proofs of the contrary: whatever the starting point, your local search can be stuck in solutions far away from the optimum. Here "local" means that each iteration must be done in polynomial time. Check the seminal paper "On the Complexity of Local Search for the Traveling Salesman Problem" by Papadimitriou and Steiglitz on ...

5

The book seems to have left out a few steps. It's important to realize that $$\frac{3}{2}a + 2b + \sqrt{2(n-2)ab}$$ is not a valid upper bound on the longest tour, even for $n\ge 2$. That can be seen by simply setting $n=2$, which reduces the above to $$\frac{3}{2}a + 2b$$ then setting $a=6,b=1$. If we put our 2 points of $X$ into ends of a side of ...

5

From the first look, you have an heterogeneous multi-depot site-dependent vehicle routing problem with time windows. I think you can use our solver for the deterministic variant of your problem: https://vrpsolver.math.u-bordeaux.fr. Efficiency of the solver of course depends on the size of your instances. An exact approach may be useful for you to estimate ...

Only top voted, non community-wiki answers of a minimum length are eligible


text:
# Atomic models of countable complete theories (without finite models) posessing a prime model

I would very much appreciate a hint as I have currently found myself stuck with exercise 13.2.2 in 'Introduction to Model Theory' by Philipp Rothmaler. Before relaying the problem I should perhaps also point out that in this text all theories are defined to be consistent as well as deductively closed.

The problem is as follows:

Suppose $$T$$ is a countable complete theory without finite models. Show that if $$T$$ has an (elementarily) prime model which is not minimal then $$T$$ has an atomic model of power $$\aleph_1$$.

Certainly, if $$\mathfrak{N}$$ is a prime model of $$T$$ then $$\mathfrak{N}$$ is unique up to isomorphism as well as atomic (and non-minimal by assumption). I guess the idea is to judiciously construct an uncountable atomic model out of countable atomic models and making use of the downwards Löwenheim-Skolem theorem but I am certainly missing something.

Hint: Build an elementary chain $$(M_\alpha)_{\alpha<\aleph_1}$$ of countable models, with $$M_\alpha$$ a proper elementary substructure of $$M_\beta$$ for all $$\alpha<\beta$$, and such that each $$M_\alpha$$ is isomorphic to the prime model $$M$$. Show that the union of this chain is atomic and has cardinality $$\aleph_1$$.

To handle the limit step of the transfinite construction, you will need to use the fact that a countable model is atomic if and only if it is prime, and countable prime models are unique up to isomorphism if they exist.

• Dangit, beat me to it! Jan 25, 2020 at 20:21
• @NoahSchweber Well, the OP only asked for a hint - and I was able to give write a hint quickly than your more complete answer. :0) Jan 25, 2020 at 20:22
• Quick question: do we actually need that countable prime models are unique? It seems to me that it's enough to observe that if one countable prime model is non-minimal, then they all are (which is basically trivial). Jan 25, 2020 at 20:44
• @NoahSchweber You're right, that observation suffices. I guess it depends on whether you prefer to take one line to cite a nontrivial result you already know or two lines to explain a trivial observation, heh. Jan 25, 2020 at 20:56

Suppose $$\mathfrak{N}$$ is a non-minimal prime model of its theory. Then there is a proper elementary substructure of $$\mathfrak{N}$$ which is isomorphic to $$\mathfrak{N}$$.

Turning this around, we get: if $$\mathfrak{A}\cong\mathfrak{N}$$ then there is a proper elementary extension of $$\mathfrak{A}$$ also isomorphic to $$\mathfrak{N}$$.

The naive idea at this point is to iterate this: build an increasing elementary chain of copies of $$\mathfrak{N}$$ of length $$\omega_1$$. Every element of the union will have its type determined (by elementarity) by the model it appears in, and since all the models in the chain are atomic that type will be principal. So the result will be atomic (and clearly of size $$\aleph_1$$).

However, it's not that simple: consider what happens at "stage $$\omega$$" of the chain. We have $$\mathfrak{A}_0\prec\mathfrak{A}_1\prec\mathfrak{A}_2\prec ...$$ each isomorphic to $$\mathfrak{N}$$, and we now need to argue that $$\bigcup_{i\in\omega}\mathfrak{A}_i$$ is, or can be elementarily embedded in a structure which is, isomorphic to $$\mathfrak{N}$$ again. And in fact there has to be a subtlety here, since the exercise is not true if we replace $$\aleph_1$$ with $$\aleph_2$$ ...


text:
# Is polar coordinates enough to prove that a limit exists

Somewhat of a basic question but I failed to find an answer or come up with a formal one myself.

Suppose I want to find the limit $\lim_{{(x,y)} \to {(0,0)}}f(x,y)$ using spherical coordinates $x:=r\cos \theta$, $y:= r\sin\theta$. Suppose I found that $\lim_{r \to 0} f(r,\theta)$ exists and is equal to $\alpha$ regardless of $\theta$. Did I really cover every possible path? Can we say for sure that the limit is $\alpha$? maybe some other limit exists in another path that we didn't cover.

For example, take $\lim_{(x,y) \to (0,0)}\frac{x^2y}{x^2+y^2} = \lim_{r\to 0}\frac{r^3\cos^2\theta \sin \theta}{r^2} = \lim_{r \to 0}r\cos^2 \theta \sin \theta = 0$.

I agree that IF the limit exists, it has to be zero. But maybe there is some path we didn't cover and from that path the limit is something else?

• the definition of continuity at $(0,0)$ doesn't involve "every paths" but only says : for every $\epsilon > 0$ there is $\delta$ such that $|(x,y)|< \delta \implies |f(x,y)-f(0,0)| < \epsilon$ – reuns Feb 23 '16 at 23:08

I would like to point you to the answer I gave here for an elaborate explaination on the use of $\lim\limits_{r\to0}$. To sum up what is said there; The problem is not that $\lim\limits_{r\to 0}f(r,\theta)$ only considers straight lines, the problem is that $\lim\limits_{r\to 0}f(r,\theta)$ is not what you probably think it is. $f(r,\theta)$ is a function of two variables, and letting $r\to 0$ means that we are approaching the line $r=0$ in the domain $[0,\infty)\times[0,2\pi)\subset \mathbb R^2$. And we commonly do not have many techniques for evaluating limits of this sort.

For instance, you seem to evealuate $\lim\limits_{r\to 0}r\cos^2\theta\sin\theta$ by substituting $r=0$. But this technique (limit evaluation by substitution) is something that is usually only proven to be valid for point-continous functions. It cannot easily be extended to apply to limits of the kind $\lim\limits_{r\to 0}f(r,\theta)$.

What you can do is argue that when we choose $\delta=\varepsilon$, then $$0<r<\delta\implies \vert r\cos^2\theta \sin \theta \vert<\delta \underbrace{\vert \cos^2 \theta \sin \theta\vert}_{\leq 1}<\varepsilon.$$ This does prove that $\lim\limits_{r\to 0}f(r,\theta)=0$. (Mind that you need to treat the cases where $\cos^2\theta\sin\theta=0$ with care.)

• This answer should be chosen as the best answer. Truly. – Eric Dec 12 '17 at 14:57

The fine point is in the phrase "regardless of $\theta$". Let $f$ be the characteristic function of the set $$A:=\left\{{1\over k}\biggl(\cos{1\over k},\sin{1\over k}\biggr)\>\biggm|\>k\in{\mathbb N}_{\geq1}\right\}\ .$$ Then $\lim_{r\to0}\tilde f(r,\theta)=0$, regardless of $\theta$, but the $\lim_{(x,y)\to(0,0)} f(x,y)$ does not exist.

If, however, you can prove that for some $(x,y)\mapsto g(x,y)$ defined in a punctured neighborhood of $(0,0)$ you have $$|g(r\cos\theta,r\sin\theta)|\leq q(r)\quad \wedge\quad \lim_{r\to0}q(r)=0$$ then you may conclude that in fact $\lim_{(x,y)\to(0,0)} g(x,y)=0$.

You should probably read the question posted here, as well as my answer to that question. The problem is that if we write $f(r;\theta)$, then taking $$\lim_{r \to 0} f(r;\theta)$$ can be misleading, because this considers only straight-line paths to the origin unless you also permit $\theta$ to vary as a function of $r$; i.e., to consider $$f(r;\theta(r))$$ for arbitrary functions $\theta(r)$.

You are confining to the origin of coordinate system in either case. When real $r = \sqrt{x^2+y^2}=0$, both $x$ and $y$ are zero. ( $r$ is zero for all $\theta$), and so it suffices.


text:
## Thursday, 18 February 2016

### On This Day in Math - February 18

##### Leon Battista Alberti, De pictura and Elementa *Museo Galileo
The power of mathematics rests on its evasion of all unnecessary thought and on its wonderful saving of mental operations.
~Ernst Mach

The 49th day of the year; lots of numbers are squareful (they are divisible by a square number) but 49 is the smallest number so that it, and both its neighbors are squareful. (Many interesting questions arise for students.. what's next, can there be four in a row?, etc)

And Prof. William D Banks of the University of Missouri has recently proved that every integer in base ten is the sum of 49 or less palindromes. (August 2015) (Building on Prof. Banks groundbreaking work, by February 22, 2016 JAVIER CILLERUELO AND FLORIAN LUCA had proved that for any base > 4
EVERY POSITIVE INTEGER IS A SUM OF THREE PALINDROMES )

The 49th Mersenne prime is discovered. On Jan 19th, 2016 The GIMPS program announced a new "largest known" prime, 274,207,281 -1. called M74,207,281 for short, the number has 22,338,618 digits.

EVENTS
3102 B.C. The Kaliyuga begins according to the Indian mathematician Aryabhata (born A.D. 476). He believed all astronomical phenomena were periodic, with period 4,320,000= 20 × 603 years, and that all the planets had mean longitude zero on this date. [College Mathematics Journal, 16 (1985), p. 169.] *VFR

1670 “Joannes Georgius Pelshower [Regimontanus Borussus] giving me a visit, and desiring an example of the like, I did that night propose to myself in the dark without help to my memory a number in 53 places: 2468135791011121411131516182017192122242628302325272931 of which I extracted the square root in 27 places: 157103016871482805817152171 proxim´e; which numbers I did not commit to paper till he gave me another visit, March following, when I did from memory dictate them to him.” So wrote John Wallis. [American Journal of Psychology, 4(1891), 38] *VFR

1673: Robert Hooke writes in his Journal: "Bought Copernicus tower hill 2sh " *@HookesLondon Thony Christie points out that current first editions run about $2,500,000$ GB Pounds.

1727 Leonhard Euler defends his De Sono essay in a public disputation at the law auditorium at Basal. His paper had been submitted as his "habilitationsschrift", part of his application for the Physics Professorship at Basal. Fortunately, he did not get the position, and soon departed for a position at Petersburg Academy of Science in Russia. Among other competitors overlooked for the position was Jakob Hermann. *Ronald S. Calinger; Leonhard Euler: Mathematical Genius in the Enlightenment

1772 the Royal Danish Academy of Sciences and Letters presented Alexander Wilson with a gold medal for his work on sunspots. Wilson was a Scottish surgeon, type-founder, astronomer, mathematician and meteorologist and the first scientist to record the use of kites in meteorological investigations. Wilson noted that sunspots viewed near the edge of the Sun's visible disk appear depressed below the solar surface, a phenomenon referred to as the Wilson effect. When the Royal Danish Academy of Sciences and Letters announced a prize to be awarded for the best essay on the nature of solar spots, Wilson submitted an entry which won. *Wik

1879 “I will do the same for the young women that I do for the young men. I shall take pleasure in giving gratuitous instruction to any person whom I ﬁnd competent to receive it. I give no elementary instruction, but only in the higher mathematics.” Benjamin Peirce to Arthur V. Gilman, president of Harvard. [Scripta Mathematica, 11(1945), 259
*VFR

1879 J. J. Sylvester, in a lecture at the Peabody Institute in Baltimore, read “Rosalind”, a mock-sentimental poem of four hundred lines all ending in “ind”. For the ﬁrst few lines of this dreadful poem, see Osiris, 1(1936), p. 106. *VFR Encyclopedia.com says that Sylvester was the author of this poem, and another which had two hundred lines rhyming with “Winn.” These were products of his later residence in Baltimore. Sylvester had perhaps a better appreciation of music.

In 1913, chemist Frederick Soddy introduced the term "isotope". Soddy was an English chemist and physicist who received the Nobel Prize for Chemistry in 1921 for investigating radioactive substances. He suggested that different elements produced in different radioactive transformations were capable of occupying the same place on the Periodic Table, and on 18 Feb 1913 he named such species "isotopes" from Greek words meaning "same place." He is credited, along with others, with the discovery of the element protactinium in 1917. *TIS He also wrote the mathematical poem, The Kiss Precise, which includes a solution to Descartes Circle Problem. the poem begins:
For pairs of lips to kiss maybe
Involves no trigonometry.
'Tis not so when four circles kiss
Each one the other three.
To bring this off the four must be
As three in one or one in three.
If one in three, beyond a doubt
Each gets three kisses from without.
If three in one, then is that one
Thrice kissed internally.
The complete poem and more about the history of the problem can be found here.

1930 Clyde Tombaugh (1906–1997) discovered Pluto on photographic plates under the direction of V M Slipher at the Lowell Observatory at Flagstaff, Az. For 45 minutes, before he showed his superiors, he was the only person in the world who knew it existed. When he later went to college he was not allowed to take Astronomy I, the instructor thinking it unsuitable for the discoverer of a planet. (On August 24th of 2006 the International Astronomical Union decided to rescind Pluto’s status as a planet and reclassify it as another entity called a “dwarf planet”. ) *FFF, pg 537

2006 The game of Connect Four was first solved by James D. Allen (Oct 1, 1988), and independently by Victor Allis (Oct 16, 1988). First player can force a win. Strongly solved by John Tromp's 8-ply database (Feb 4, 1995). It was weakly solved for all boardsizes where width+height is at most 15 (Feb 18, 2006). *Wik

BIRTHS
1201 Muhammad ibn Muhammad ibn al-Hasan al-Tusi (18 Feb 1201; 26 Jun 1274 at age 73) Persian philosopher, scientist, mathematician and astronomer who made outstanding contributions in his era. When The Mongol invasion, started by Genghis Khan, reached him in 1256, he escaped likely death by joining the victorious Mongols as a scientific adviser. He used an observatory built at Maragheh (finished 1262), assisted by Chinese astronomers. It had various instruments such as a 4 meter wall quadrant made from copper and an azimuth quadrant which was Tusi's own invention. Using accurately plotted planetary movements, he modified Ptolemy's model of the planetary system based on mechanical principles. The observatory and its library became a center for a wide range of work in science, mathematics and philosophy. He was known by the title Tusi from his place of birth (Tus)*TIS

1404 Leon Battista Alberti (18 Feb 1404; 25 Apr 1472 at age 68) Italian artist and geometrist who “wrote the book,” the first general treatise Della Pictura (1434) on the the laws of perspective, establishing the science of projective geometry. Alberti also worked on maps (again involving his skill at geometrical mappings) and he collaborated with Toscanelli who supplied Columbus with the maps for his first voyage. He also wrote the first book on cryptography which contains the first example of a frequency table. *TIS
. This noted architect took up the study of mathematics for relaxation. He contributed to the study of perspective. *VFR

1677 Jacques Cassini (18 Feb 1677; 16 Apr 1756 at age 79) French astronomer whose direct measurement of the proper motions of the stars (1738) disproved the ancient belief in the unchanging sphere of the stars. He also studied the moons of Jupiter and Saturn and the structure of Saturn's rings. His two major treatises on these subject appeared in 1740: Elements of Astronomy and Astronomical Tables of the Sun, Moon, Planets, Fixed Stars, and Satellites of Jupiter and Saturn. He also wrote about electricity, barometers, the recoil of firearms, and mirrors. He was the son of astronomer, mathematician and engineer Giovanni Cassini (1625-1712) with whom he made numerous geodesic observations. Eventually, he took over his father's duties as head of the Paris Observatory.*TIS Cassini was born at the Paris Observatory and died at Thury, near Clermont. Admitted at the age of seventeen to membership of the French Academy of Sciences, he was elected in 1696 a fellow of the Royal Society of London, and became maître des comptes in 1706. *Wik

1745 Count Alessandro Giuseppe Antonio Anastasio Volta (18 Feb 1745; 5 Mar 1827 at age 82) Italian physicist who invented the electric battery (1800), which for the first time enabled the reliable, sustained supply of current. His voltaic pile used plates of two dissimilar metals and an electrolyte, a number of alternated zinc and silver disks, each separated with porous brine-soaked cardboard. Previously, only discharge of static electricity had been available, so his device opened a new door to new uses of electricity. Shortly thereafter, William Nicholson decomposed water by electrolysis. That same process later enabled Humphry Davy to isolate potassium and other metals. Volta also invented the electrophorus, the condenser and the electroscope. He made important contributions to meteorology. His study of gases included the discovery of methane. The volt, a unit of electrical measurement, is named after him.*TIS

1832 Octave Chanute(18 Feb 1832, 23 Nov 1910) U.S. aeronaut whose work and interests profoundly influenced Orville and Wilbur Wright and the invention of the airplane. Octave Chanute was a successful engineer who took up the invention of the airplane as a hobby following his early retirement. Knowing how railroad bridges were strengthened, Chanute experimented with box kites using the same basic strengthening method, which he then incorporated into wing design of gliders. Through thousands of letters, he drew geographically isolated pioneers into an informal international community. He organized sessions of aeronautical papers for the professional engineering societies that he led; attracted fresh talent and new ideas into the field through his lectures; and produced important publications. *TIS The town of Chanute, Kansas is named after him, as well as the former Chanute Air Force Base near Rantoul, Illinois, which was decommissioned in 1993. The former Base, now turned to peacetime endeavors, includes the Octave Chanute Aerospace Museum, detailing the history of aviation and of Chanute Air Force base. He was buried in Springdale Cemetery, Peoria, Illinois. *Wik

1838 Ernst Mach (18 Feb 1838; 19 Feb 1916 at age 77) Austrian physicist and philosopher who established important principles of optics, mechanics, and wave dynamics. His early physical works were devoted to electric discharge and induction. Between 1860 and 1862 he studied in depth the Doppler Effect by optical and acoustic experiments. He introduced the "Mach number" for the ratio of speed of object to speed of sound is named for him. When supersonic planes travel today, their speed is measured in terms that keep Mach's name alive. His lifetime interest, however, was in psychology and human perception. He supported the view that all knowledge is a conceptual organization of the data of sensory experience (or observation). *TIS

1844 Jacob Lüroth (18 Feb 1844 in Mannheim, Germany - 14 Sept 1910 in Munich, Germany) Lüroth was taught by Hesse and Clebsch and continued to develop their work on geometry and invariants. He published results in the areas of analytic geometry, linear geometry and continued the directions of his teachers in his publications on invariant theory. In 1869 Lüroth discovered the "Lüroth quartic". This came out of an investigation he was carrying out into when a ternary quartic form could be represented as the sum of five fourth powers of linear forms.
Some of his work on rational curves, published in Mathematische Annalen in 1876, was extended to surfaces by Castelnuovo in 1895. In 1883 Lüroth published his method on constructing a Riemann surface for a given algebraic curve.
Lüroth also worked on the big problem of the topological invariance of dimension. He made some useful progress but this difficult problem was not completely solved until the work of Brouwer in 1911.
Among his other work, Lüroth undertook editing. He was an editor of the complete works of Hesse and of Grassmann. He also has some fine results on logic, a topic he worked on in collaboration with his friend Ernst Schröder.
Von Staudt's ideas of geometry interested Lüroth and he further developed von Staudt's complex geometry. He published Grundriss der Mechanik in 1881. This mechanics book makes heavy use of the vector calculus. *sau

1871 George Udny Yule (18 Feb 1871 in Morham (near Haddington), Scotland - 26 June 1951 in Cambridge, Cambridgeshire, England) graduated in Engineering from University College London and then studied in Bonn. He worked with Karl Pearson on the statistics of regression and correlation. He took a post with an examinations board before being appointed to a Cambridge fellowship. He is best known for his book: Introduction to the Theory of Statistics.*SAU

DEATHS
901 Al-Sabi Thabit ibn Qurra al-Harrani (born c. 836, 18 Feb 901) was a Mesopotamian scholar and mathematician who greatly contributed to preparing the way for such important mathematical discoveries as the extension of the concept of number to (positive) real numbers, integral calculus, theorems in spherical trigonometry, analytic geometry, and non-euclidean geometry. In astronomy he was one of the first reformers of the Ptolemaic system, writing Concerning the Motion of the Eighth Sphere. He believed (wrongly) that the motion of the equinoxes oscillates. Including observations of the Sun, eight complete treatises by Thabit on astronomy have survived. In mechanics he was a founder of statics. He wrote The Book on the Beam Balance in which he finds the conditions for the equilibrium of a heavy beam. *TIS

1851 Karl Gustav Jacob Jacobi (10 Dec 1804; 18 Feb 1851) German mathematician who, with the independent work of Niels Henrik Abel of Norway, founded the theory of elliptic functions. He also worked on Abelian functions and discovered the hyperelliptic functions. Jacobi applied his work in elliptic functions to number theory. He also investigated mathematical analysis and geometry. Jacobi carried out important research in partial differential equations of the first order and applied them to the differential equations of dynamics. His work on determinants is important in dynamics and quantum mechanics and he studied the functional determinant now called the Jacobian. *TIS He died from smallpox, in his 47th year.*VFR

1856 Baron Wilhelm von Biela (19 Mar 1782, 18 Feb 1856 at age 73) Austrian astronomer who was known for his measurement (1826) of a previously known comet as having an orbital period of 6.6 years. Subsequently, known as Biela's Comet, it was observed to break in two (1846), and in 1852 the fragments returned as widely separated twin comets that were not seen again. However, in 1872 and 1885, bright meteor showers (known as Andromedids, or Bielids) were observed when the Earth crossed the path of the comet's known orbit. This observation provided the first concrete evidence for the idea that some meteors are composed of fragments of disintegrated comets.*TIS

1877 Charles Henry Davis (16 Jan 1807; 18 Feb 1877) U.S. naval officer and scientist who published several hydrographic studies, was a superintendent of the Naval Observatory (1865–67, 1874–77) and worked to further scientific progress. Between his naval duties at sea, he studied mathematics at Harvard. He made the first comprehensive survey of the coasts of Massachusetts, Rhode Island, and Maine, including the intricate Nantucket shoals area. He helped establish and then supervised the preparation of the American Nautical Almanac (1849) for several years. Davis was a co-founder of the National Academy of Sciences (1863), and wrote several scientific books.*TIS

1899 (Marius) Sophus Lie (17 Dec 1842; 18 Feb 1899) was a Norwegian mathematician who made significant contributions to the theories of algebraic invariants, continuous groups of transformations and differential equations. Lie groups and Lie algebras are named after him. Lie was in Paris at the outbreak of the French-German war of 1870. Lie left France, deciding to go to Italy. On the way however he was arrested as a German spy and his mathematics notes were assumed to be coded messages. Only after the intervention of French mathematician, Gaston Darboux, was Lie released and he decided to return to Christiania, Norway, where he had originally studied mathematics to continue his work. *TIS

1900 Eugenio Beltrami (November 16, 1835, Cremona – February 18, 1900, Rome) was an Italian mathematician notable for his work concerning differential geometry and mathematical physics. His work was noted especially for clarity of exposition. He was the first to prove consistency of non-Euclidean geometry by modeling it on a surface of constant curvature, the pseudosphere, and in the interior of an n-dimensional unit sphere, the so-called Beltrami–Klein model. He also developed singular value decomposition for matrices, which has been subsequently rediscovered several times. Beltrami's use of differential calculus for problems of mathematical physics indirectly influenced development of tensor calculus by Gregorio Ricci-Curbastro and Tullio Levi-Civita.*Wik
Beltrami studied elasticity, wave theory, optics, thermodynamics, and potential theory, and was among the first to explore the concepts of hyperspace and time as a fourth dimension. His investigations in the conduction of heat led to linear partial differential equations. Some of Beltrami's last work was on a mechanical interpretation of Maxwell's equations. *TIS

1944 Charles Benedict Davenport (1 Jun 1866, 18 Feb 1944 at age 77) American zoologist who contributed substantially to the study of eugenics (the improvement of populations through breeding) and heredity and who pioneered the use of statistical techniques in biological research. Partly as a result of breeding experiments with chickens and canaries, he was one of the first, soon after 1902, to recognize the validity of the newly discovered Mendelian theory of heredity. In Heredity in Relation to Eugenics (1911), he compiled evidence concerning the inheritance of human traits, on the basis of which he argued that the application of genetic principles would improve the human race. These data were at the heart of his lifelong promotion of eugenics, though he muddled science with social philosophy. *TIS

1957 Henry Norris Russell (25 Oct 1877; 18 Feb 1957) American astronomer and astrophysicist who showed the relationship between a star's brightness and its spectral type, in what is usually called the Hertzsprung-Russell diagram, and who also devised a means of computing the distances of binary stars. As student, professor, observatory director, and active professor emeritus, Russell spent six decades at Princeton University. From 1921, he visited Mt. Wilson Observatory annually. He analyzed light from eclipsing binary stars to determine stellar masses. Russell measured parallaxes and popularized the distinction between giant stars and "dwarfs" while developing an early theory of stellar evolution. Russell was a dominant force in American astronomy as a teacher, writer, and advisor. *TIS

1967 Julius Robert Oppenheimer (22 Apr 1904, 18 Feb 1967 at age 62) was an American theoretical physicist and science administrator, noted as director of the Los Alamos laboratory during development of the atomic bomb (1943-45) and as director of the Institute for Advanced Study, Princeton (1947-66). Accusations as to his loyalty and reliability as a security risk led to a government hearing that resulted the loss of his security clearance and of his position as adviser to the highest echelons of the U.S. government. The case became a cause célèbre in the world of science because of its implications concerning political and moral issues relating to the role of scientists in government. *TIS

Credits :
*CHM=Computer History Museum
*FFF=Kane, Famous First Facts
*NSEC= NASA Solar Eclipse Calendar
*RMAT= The Renaissance Mathematicus, Thony Christie
*SAU=St Andrews Univ. Math History
*TIA = Today in Astronomy
*TIS= Today in Science History
*VFR = V Frederick Rickey, USMA
*Wik = Wikipedia
*WM = Women of Mathematics, Grinstein & Campbell


text:
# American Institute of Mathematical Sciences

June  2017, 7(2): 305-345. doi: 10.3934/mcrf.2017011

## Exact controllability of linear stochastic differential equations and related problems

 1 School of Mathematics and Statistics, Southwest University, Chongqing 400715, China 2 School of Mathematics and Statistics, School of Information Science and Engineering, Central South University, Changsha 410075, China 3 Department of Mathematics, University of Central Florida, Orlando, FL 32816, USA 4 School of Mathematics, Shandong University, Jinan 250100, China

∗ Corresponding author: Zhiyong Yu.

Received  January 2017 Published  April 2017

Fund Project: the National Natural Science Foundation of China (11471192, 11371375, 11526167), the Fundamental Research Funds for the Central Universities (SWU113038, XDJK2014C076), the Nature Science Foundation of Shandong Province (JQ201401), the Natural Science Foundation of CQCSTC (2015jcyjA00017), China Postdoctoral Science Foundation and Central South University Postdoctoral Science Foundation, and NSF Grant DMS-1406776.

A notion of $L^p$-exact controllability is introduced for linear controlled (forward) stochastic differential equations with random coefficients. Several sufficient conditions are established for such kind of exact controllability. Further, it is proved that the $L^p$-exact controllability, the validity of an observability inequality for the adjoint equation, the solvability of an optimization problem, and the solvability of an $L^p$-type norm optimal control problem are all equivalent.

Citation: Yanqing Wang, Donghui Yang, Jiongmin Yong, Zhiyong Yu. Exact controllability of linear stochastic differential equations and related problems. Mathematical Control & Related Fields, 2017, 7 (2) : 305-345. doi: 10.3934/mcrf.2017011
##### References:
 [1] R. Buckdahn, M. Quincampoix and G. Tessitore, A characterization of approximately controllable linear stochastic differential equations, , (). doi: 10.1201/9781420028720.ch6. Google Scholar [2] S. Chen, X. Li, S. Peng and J. Yong, On stochastic linear controlled systems, Preprint, 1993.Google Scholar [3] M.M. Connors, Controllability of discrete, linear, random dynamical systems, SIAM J. Control, 5 (1967), 183-210. doi: 10.1137/0305012. Google Scholar [4] E.D. Denman and A.N. Beavers,Jr., The matrix sign function and computations in systems, Appl. Math. Comput., 2 (1976), 63-94. doi: 10.1016/0096-3003(76)90020-5. Google Scholar [5] M. Ehrhardt and W. Kliemann, Controllability of linear stochastic systems, , (). doi: 10.1016/0167-6911(82)90012-3. Google Scholar [6] N. El Karoui, S. Peng and M.C. Quenez, Backward stochastic differential equations in finance, Math. Finance, 7 (1997), 1-71. doi: 10.1111/1467-9965.00022. Google Scholar [7] H. O. Fattorini, Infinite-Dimensional Optimization and Control Theory Cambridge Univ. Press, Cambridge, 1999. doi: 10.1017/CBO9780511574795. Google Scholar [8] H.O. Fattorini, Time and norm optimal controls: A survey of recent results and open problems, Acta Math. Sci. Ser. B Engl. Ed., 31 (2011), 2203-2218. doi: 10.1016/S0252-9602(11)60394-9. Google Scholar [9] G. B. Folland, Real Analysis: Modern Techniques and Their Applications, 2nd Edition John Wiley & Sons, New York, 1999. Google Scholar [10] B. Gashi, Stochastic minimum-energy control, Systems Control Lett., 85 (2015), 70-76. doi: 10.1016/j.sysconle.2015.08.012. Google Scholar [11] D. Goreac, A Kalman-type condition for stochastic approximate controllability, C. R. Math. Acad. Sci. Paris, 346 (2008), 183-188. doi: 10.1016/j.crma.2007.12.008. Google Scholar [12] M. Gugat and G. Leugering, $L^∞$-norm minimal control of the wave equation: On the weakness of the bang-bang principle, ESAIM Control Optim. Calc. Var., 14 (2008), 254-283. doi: 10.1051/cocv:2007044. Google Scholar [13] E. B. Lee and L. Markus, Foundations of Optimal Control Theory John Wiley & Sons, 1967. Google Scholar [14] J.L. Lions, Exact controllability, stabilizability and perturbations for distributed systems, SIAM Rev., 30 (1988), 1-68. doi: 10.1137/1030001. Google Scholar [15] J. L. Lions, Controlabilité Exacte, Perturbations et Stabilisation de Systémes Distribués Masson, Paris, RMA 8,1988. Google Scholar [16] F. Liu and S. Peng, On controllability for stochastic control systems when the coefficient is time-variant, J. Syst. Sci. Complex., 23 (2010), 270-278. doi: 10.1007/s11424-010-8158-x. Google Scholar [17] Q. Lü, J. Yong and X. Zhang, Representation of Itô integrals by Lebesgue/Bochner integrals, J. Eur. Math. Soc., 14 (2012), 1795-1823. doi: 10.4171/JEMS/347. Google Scholar [18] S. Peng, Backward stochastic differential equation and exact controllability of stochastic control systems, Progr. Natur. Sci. (English Ed.), 4 (1994), 274-284. Google Scholar [19] D.L. Russell, Controllability and stabilizability theory for linear partial differential equations, Recent Progress and open questions, SIAM Rev., 20 (1978), 639-739. doi: 10.1137/1020095. Google Scholar [20] Y. Shi, T. Wang and J. Yong, Mean-field backward stochastoic Volterra integral equations, Discrete Continuous Dyn. Systems, Ser. B, 18 (2013), 1929-1967. doi: 10.3934/dcdsb.2013.18.1929. Google Scholar [21] Y. Sunahara, S. Aihara and K. Kishino, On the stochastic observability and controllability for non-linear systems, Int. J Control, 22 (1975), 65-82. doi: 10.1080/00207177508922061. Google Scholar [22] G. Wang and Y. Xu, Equivalence of three different kinds of optimal control problems for heat equations and its applications, SIAM J. Control Optim., 51 (2013), 848-880. doi: 10.1137/110852449. Google Scholar [23] G. Wang and E. Zuazua, On the equivalence of minimal time and minimal norm controls for internally controlled heat equations, SIAM J. Control Optim., 50 (2012), 2938-2958. doi: 10.1137/110857398. Google Scholar [24] Y. Wang and C. Zhang, The norm optimal control problem for stochastic linear control systems, ESAIM Control Optim. Calc. Var., 21 (2015), 399-413. doi: 10.1051/cocv/2014030. Google Scholar [25] W. M. Wonham, Linear Multivariable Control: A Geometric Approach, 3rd Edition Springer Verlag, New York, 1985. doi: 10.1007/978-1-4612-1082-5. Google Scholar [26] J. Yong and X. Y. Zhou, Stochastic Controls: Hamiltonian Systems and HJB Equations Springer, New York, 1999. doi: 10.1007/978-1-4612-1466-3. Google Scholar [27] K. Yosida, Functional Analysis Springer-Verlag, Berlin, New York, 1980. Google Scholar [28] J. Zabczyk, Controllability of stochastic linear systems, Systems Control Lett., 1 (1981), 25-31. doi: 10.1016/S0167-6911(81)80008-4. Google Scholar [29] E. Zuazua, Controllability of Partial Differential Equations manuscript, 2006.Google Scholar

show all references

##### References:
 [1] R. Buckdahn, M. Quincampoix and G. Tessitore, A characterization of approximately controllable linear stochastic differential equations, , (). doi: 10.1201/9781420028720.ch6. Google Scholar [2] S. Chen, X. Li, S. Peng and J. Yong, On stochastic linear controlled systems, Preprint, 1993.Google Scholar [3] M.M. Connors, Controllability of discrete, linear, random dynamical systems, SIAM J. Control, 5 (1967), 183-210. doi: 10.1137/0305012. Google Scholar [4] E.D. Denman and A.N. Beavers,Jr., The matrix sign function and computations in systems, Appl. Math. Comput., 2 (1976), 63-94. doi: 10.1016/0096-3003(76)90020-5. Google Scholar [5] M. Ehrhardt and W. Kliemann, Controllability of linear stochastic systems, , (). doi: 10.1016/0167-6911(82)90012-3. Google Scholar [6] N. El Karoui, S. Peng and M.C. Quenez, Backward stochastic differential equations in finance, Math. Finance, 7 (1997), 1-71. doi: 10.1111/1467-9965.00022. Google Scholar [7] H. O. Fattorini, Infinite-Dimensional Optimization and Control Theory Cambridge Univ. Press, Cambridge, 1999. doi: 10.1017/CBO9780511574795. Google Scholar [8] H.O. Fattorini, Time and norm optimal controls: A survey of recent results and open problems, Acta Math. Sci. Ser. B Engl. Ed., 31 (2011), 2203-2218. doi: 10.1016/S0252-9602(11)60394-9. Google Scholar [9] G. B. Folland, Real Analysis: Modern Techniques and Their Applications, 2nd Edition John Wiley & Sons, New York, 1999. Google Scholar [10] B. Gashi, Stochastic minimum-energy control, Systems Control Lett., 85 (2015), 70-76. doi: 10.1016/j.sysconle.2015.08.012. Google Scholar [11] D. Goreac, A Kalman-type condition for stochastic approximate controllability, C. R. Math. Acad. Sci. Paris, 346 (2008), 183-188. doi: 10.1016/j.crma.2007.12.008. Google Scholar [12] M. Gugat and G. Leugering, $L^∞$-norm minimal control of the wave equation: On the weakness of the bang-bang principle, ESAIM Control Optim. Calc. Var., 14 (2008), 254-283. doi: 10.1051/cocv:2007044. Google Scholar [13] E. B. Lee and L. Markus, Foundations of Optimal Control Theory John Wiley & Sons, 1967. Google Scholar [14] J.L. Lions, Exact controllability, stabilizability and perturbations for distributed systems, SIAM Rev., 30 (1988), 1-68. doi: 10.1137/1030001. Google Scholar [15] J. L. Lions, Controlabilité Exacte, Perturbations et Stabilisation de Systémes Distribués Masson, Paris, RMA 8,1988. Google Scholar [16] F. Liu and S. Peng, On controllability for stochastic control systems when the coefficient is time-variant, J. Syst. Sci. Complex., 23 (2010), 270-278. doi: 10.1007/s11424-010-8158-x. Google Scholar [17] Q. Lü, J. Yong and X. Zhang, Representation of Itô integrals by Lebesgue/Bochner integrals, J. Eur. Math. Soc., 14 (2012), 1795-1823. doi: 10.4171/JEMS/347. Google Scholar [18] S. Peng, Backward stochastic differential equation and exact controllability of stochastic control systems, Progr. Natur. Sci. (English Ed.), 4 (1994), 274-284. Google Scholar [19] D.L. Russell, Controllability and stabilizability theory for linear partial differential equations, Recent Progress and open questions, SIAM Rev., 20 (1978), 639-739. doi: 10.1137/1020095. Google Scholar [20] Y. Shi, T. Wang and J. Yong, Mean-field backward stochastoic Volterra integral equations, Discrete Continuous Dyn. Systems, Ser. B, 18 (2013), 1929-1967. doi: 10.3934/dcdsb.2013.18.1929. Google Scholar [21] Y. Sunahara, S. Aihara and K. Kishino, On the stochastic observability and controllability for non-linear systems, Int. J Control, 22 (1975), 65-82. doi: 10.1080/00207177508922061. Google Scholar [22] G. Wang and Y. Xu, Equivalence of three different kinds of optimal control problems for heat equations and its applications, SIAM J. Control Optim., 51 (2013), 848-880. doi: 10.1137/110852449. Google Scholar [23] G. Wang and E. Zuazua, On the equivalence of minimal time and minimal norm controls for internally controlled heat equations, SIAM J. Control Optim., 50 (2012), 2938-2958. doi: 10.1137/110857398. Google Scholar [24] Y. Wang and C. Zhang, The norm optimal control problem for stochastic linear control systems, ESAIM Control Optim. Calc. Var., 21 (2015), 399-413. doi: 10.1051/cocv/2014030. Google Scholar [25] W. M. Wonham, Linear Multivariable Control: A Geometric Approach, 3rd Edition Springer Verlag, New York, 1985. doi: 10.1007/978-1-4612-1082-5. Google Scholar [26] J. Yong and X. Y. Zhou, Stochastic Controls: Hamiltonian Systems and HJB Equations Springer, New York, 1999. doi: 10.1007/978-1-4612-1466-3. Google Scholar [27] K. Yosida, Functional Analysis Springer-Verlag, Berlin, New York, 1980. Google Scholar [28] J. Zabczyk, Controllability of stochastic linear systems, Systems Control Lett., 1 (1981), 25-31. doi: 10.1016/S0167-6911(81)80008-4. Google Scholar [29] E. Zuazua, Controllability of Partial Differential Equations manuscript, 2006.Google Scholar
 [1] Abdelmouhcene Sengouga. Exact boundary observability and controllability of the wave equation in an interval with two moving endpoints. Evolution Equations & Control Theory, 2020, 9 (1) : 1-25. doi: 10.3934/eect.2020014 [2] Peter I. Kogut, Olha P. Kupenko. On optimal control problem for an ill-posed strongly nonlinear elliptic equation with $p$-Laplace operator and $L^1$-type of nonlinearity. Discrete & Continuous Dynamical Systems - B, 2019, 24 (3) : 1273-1295. doi: 10.3934/dcdsb.2019016 [3] Guozhen Lu, Yunyan Yang. Sharp constant and extremal function for the improved Moser-Trudinger inequality involving $L^p$ norm in two dimension. Discrete & Continuous Dynamical Systems - A, 2009, 25 (3) : 963-979. doi: 10.3934/dcds.2009.25.963 [4] Lingyang Liu, Xu Liu. Controllability and observability of some coupled stochastic parabolic systems. Mathematical Control & Related Fields, 2018, 8 (3&4) : 829-854. doi: 10.3934/mcrf.2018037 [5] Lijuan Wang, Qishu Yan. Optimal control problem for exact synchronization of parabolic system. Mathematical Control & Related Fields, 2019, 9 (3) : 411-424. doi: 10.3934/mcrf.2019019 [6] Karina Samvelyan, Frol Zapolsky. Rigidity of the ${{L}^{p}}$-norm of the Poisson bracket on surfaces. Electronic Research Announcements, 2017, 24: 28-37. doi: 10.3934/era.2017.24.004 [7] Thierry Horsin, Peter I. Kogut, Olivier Wilk. Optimal $L^2$-control problem in coefficients for a linear elliptic equation. II. Approximation of solutions and optimality conditions. Mathematical Control & Related Fields, 2016, 6 (4) : 595-628. doi: 10.3934/mcrf.2016017 [8] Thierry Horsin, Peter I. Kogut. Optimal $L^2$-control problem in coefficients for a linear elliptic equation. I. Existence result. Mathematical Control & Related Fields, 2015, 5 (1) : 73-96. doi: 10.3934/mcrf.2015.5.73 [9] Jianhui Huang, Xun Li, Jiongmin Yong. A linear-quadratic optimal control problem for mean-field stochastic differential equations in infinite horizon. Mathematical Control & Related Fields, 2015, 5 (1) : 97-139. doi: 10.3934/mcrf.2015.5.97 [10] Giuseppe Da Prato. An integral inequality for the invariant measure of some finite dimensional stochastic differential equation. Discrete & Continuous Dynamical Systems - B, 2016, 21 (9) : 3015-3027. doi: 10.3934/dcdsb.2016085 [11] Stanisław Migórski. A note on optimal control problem for a hemivariational inequality modeling fluid flow. Conference Publications, 2013, 2013 (special) : 545-554. doi: 10.3934/proc.2013.2013.545 [12] Leszek Gasiński. Optimal control problem of Bolza-type for evolution hemivariational inequality. Conference Publications, 2003, 2003 (Special) : 320-326. doi: 10.3934/proc.2003.2003.320 [13] Hee-Dae Kwon, Jeehyun Lee, Sung-Dae Yang. Eigenseries solutions to optimal control problem and controllability problems on hyperbolic PDEs. Discrete & Continuous Dynamical Systems - B, 2010, 13 (2) : 305-325. doi: 10.3934/dcdsb.2010.13.305 [14] Piernicola Bettiol. State constrained $L^\infty$ optimal control problems interpreted as differential games. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 3989-4017. doi: 10.3934/dcds.2015.35.3989 [15] Tatsien Li, Bopeng Rao, Zhiqiang Wang. Exact boundary controllability and observability for first order quasilinear hyperbolic systems with a kind of nonlocal boundary conditions. Discrete & Continuous Dynamical Systems - A, 2010, 28 (1) : 243-257. doi: 10.3934/dcds.2010.28.243 [16] Manuel González-Burgos, Sergio Guerrero, Jean Pierre Puel. Local exact controllability to the trajectories of the Boussinesq system via a fictitious control on the divergence equation. Communications on Pure & Applied Analysis, 2009, 8 (1) : 311-333. doi: 10.3934/cpaa.2009.8.311 [17] Haiyang Wang, Zhen Wu. Time-inconsistent optimal control problem with random coefficients and stochastic equilibrium HJB equation. Mathematical Control & Related Fields, 2015, 5 (3) : 651-678. doi: 10.3934/mcrf.2015.5.651 [18] Klaus-Jochen Engel, Marjeta Kramar FijavŽ. Exact and positive controllability of boundary control systems. Networks & Heterogeneous Media, 2017, 12 (2) : 319-337. doi: 10.3934/nhm.2017014 [19] Jan-Hendrik Webert, Philip E. Gill, Sven-Joachim Kimmerle, Matthias Gerdts. A study of structure-exploiting SQP algorithms for an optimal control problem with coupled hyperbolic and ordinary differential equation constraints. Discrete & Continuous Dynamical Systems - S, 2018, 11 (6) : 1259-1282. doi: 10.3934/dcdss.2018071 [20] Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437

2018 Impact Factor: 1.292


text:
Question #c0267

Jun 7, 2017

The total volume of the mixture is 118.6 L. All the gases exert the same pressure: 1 bar.

Explanation:

STP is a pressure of 1 bar and a temperature of 0 °C.

At STP the volume of 1 mol of any gas is 22.71 L.

So, we can find the moles of each gas and then calculate the volumes.

Hydrogen

$\text{Moles" = 6.50 color(red)(cancel(color(black)("g"))) × "1 mol"/(2.016 color(red)(cancel(color(black)("g")))) = "3.224 mol}$

$\text{Volume" = 3.224 color(red)(cancel(color(black)("mol"))) × "22.71 L"/(1 color(red)(cancel(color(black)("mol")))) = "73.22 L}$

Nitrogen dioxide

$\text{Moles" = 6.50 color(red)(cancel(color(black)("g"))) × "1 mol"/(46.01 color(red)(cancel(color(black)("g")))) = "0.1413 mol}$

$\text{Volume" = 0.1413 color(red)(cancel(color(black)("mol"))) × "22.71 L"/(1 color(red)(cancel(color(black)("mol")))) = "3.208 L}$

Carbon monoxide

$\text{Moles" = 6.50 color(red)(cancel(color(black)("g"))) × "1 mol"/(28.01 color(red)(cancel(color(black)("g")))) = "0.2321 mol}$

$\text{Volume" = 0.2321 color(red)(cancel(color(black)("mol"))) × "22.71 L"/(1 color(red)(cancel(color(black)("mol")))) = "5.270 L}$

Helium

$\text{Moles" = 6.50 color(red)(cancel(color(black)("g"))) × "1 mol"/(4.003 color(red)(cancel(color(black)("g")))) = "1.624 mol}$

$\text{Volume" = 1.624 color(red)(cancel(color(black)("mol"))) × "22.71 L"/(1 color(red)(cancel(color(black)("mol")))) = "36.88 L}$

Total volume

The total volume of the gases is

$V = \text{(73.22 + 3.208 + 5.270 + 36.88) L" = "118.6 L}$

Gas Pressure

All gases are at STP, so they each exert the same pressure: 1 bar.


text:
# POJ - 2989 All Friends 极大团

 Time Limit: 1000MS Memory Limit: 65536KB 64bit IO Format: %lld & %llu

Description

Sociologists are interested in the phenomenon of "friendship". To study this property, they analyze various groups of people. For each two persons in such a group they determine whether they are friends (it is assumed that this relation is symmetric). The sociologists are mostly interested in the sets of friends. The set S of people is the set of friends if every two persons in S are friends. However, studying the sets of friends turns out to be quite complicated, since there are too many such sets. Therefore, they concentrate just on the maximal sets of friends. A set of friends S is maximal if every person that does not belong to S is not a friend with someone in S.

Your task is to determine the number of maximal sets of friends in each group. In case this number exceeds 1 000, you just need to report this -- such a group is too complicated to study.

Input

The input consists of several instances, separated by single empty lines.

The first line of each instance consists of two integers 1 ≤ n ≤ 128 and m -- number of persons in the group and number of friendship relations. Each of m following lines consists of two integers ai and bi (1 ≤ ai, bi ≤ n). This means that persons ai and bi (ai ≠ bi) are friends. Each such relationship is described at most once.

Output

The output for each instance consists of a single line containing the number of maximal sets of friends in the described group, or string "Too many maximal sets of friends." in case this number is greater than 1 000.

Sample Input

5 4
1 2
3 4
2 3
4 5

Sample Output

4

    BronKerbosch(All, Some, None):
if Some and None are both empty:
report All as a maximal clique //所有点已选完，且没有不能选的点,累加答案
for each vertex v in Some: //枚举Some中的每一个元素
BronKerbosch1(All ⋃ {v}, Some ⋂ N(v), None ⋂ N(v))
//将v加入All，显然只有与v为朋友的人才能作为备选，None中也只有与v为朋友的才会对接下来造成影响
Some := Some - {v} //已经搜过，在Some中删除，加入None
None := None ⋃ {v}

void dfs(int d, int an, int sn, int nn){
if(!sn && !nn) S++;//已经搜到了，与所选点全部有连接的点以全部放入all中

int u = some[d][1];
For(i, 1, sn){
int v = some[d][i];
if(G[u][v]) continue;//优化，只要取与当前已经搜过的点没有连接的点就可以了，因为它们肯定已经被处理过了
int tsn = 0, tnn = 0;

For(j, 1, an) all[d+1][j] = all[d][j];
all[d+1][an+1] = v; //将点v放入all中

For(j, 1, sn)
if(G[v][some[d][j]]) some[d+1][++tsn] = some[d][j];
For(j, 1, nn)
if(G[v][none[d][j]]) none[d+1][++tnn] = none[d][j];

dfs(d+1, an+1, tsn, tnn);

some[d][i] = 0; none[d][++nn] = v; //从some中取出v，放入none（判重）
}
}

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>

using namespace std;

#define MAXN (150+5)
#define INF 0x3f3f3f3f
#define Set(a, v) memset(a, v, sizeof(a))
#define For(i, a, b) for(int i = (a); i <= (int)(b); i++)

bool G[MAXN][MAXN];
int n, m, S, all[MAXN][MAXN], some[MAXN][MAXN], none[MAXN][MAXN];

void init(){
Set(G, 0);
}

void dfs(int d, int an, int sn, int nn){
if(!sn && !nn) S++;
if(S > 1000) return;

int u = some[d][1];
For(i, 1, sn){
int v = some[d][i];
if(G[u][v]) continue;
int tsn = 0, tnn = 0;

For(j, 1, an) all[d+1][j] = all[d][j];
all[d+1][an+1] = v;

For(j, 1, sn)
if(G[v][some[d][j]]) some[d+1][++tsn] = some[d][j];
For(j, 1, nn)
if(G[v][none[d][j]]) none[d+1][++tnn] = none[d][j];

dfs(d+1, an+1, tsn, tnn);

some[d][i] = 0; none[d][++nn] = v;
}
}

int main(){
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);

while(scanf("%d%d", &n, &m) != EOF){
init();

For(i, 1, m){
int u, v;
scanf("%d%d", &u, &v);
G[u][v] = G[v][u] = true;
}
For(i, 1, n) some[0][i] = i;

S = 0;
dfs(0, 0, n, 0);
if(S <= 1000) printf("%d\n", S);
else printf("Too many maximal sets of friends.\n");
}

return 0;
}

• 评论

• 下一篇
• 上一篇


text:
# Rational preferences/individual decision-making theory

I am taking advanced micro course this semester. In one of the problems we need to determine whether the preference relation is rational (i.e. complete and transitive). Since we have not really discussed the set of two-dimensional real vectors $$X=R^2$$ (non-negative), I am wondering whether these preference relations are indeed rational, and if yes, how can it be shown

(i) The relation ≽ defined by $$(x_1,x_2)$$$$(y_1,y_2)$$ if and only if $$x_1≥y_1$$ and $$x_2≥y_2$$
(ii) The relation ≽ defined by $$(x_1,x_2)$$$$(y_1,y_2)$$ if and only if $$x_1≥y_1$$
(iii) The relation ≽ defined by $$(x_1,x_2)$$$$(y_1,y_2)$$ if and only if $$\min\{x_1,x_2\} ≥ \min\{y_1,y_2\}$$
(iv) The relation ≽ defined by $$(x_1,x_2)$$$$(y_1,y_2)$$ if and only if $$x_1>y_1$$ or $$x_1=y_1$$ and $$x_2≥y_2$$

(i) Is not complete. For instance, (10,5) is not $$\succeq$$ (9,6), because $$10>9$$, but $$5<6$$. However, (9,6) is also not $$\succeq$$ (10,5) for the same reason. Hence, there exists a pair of bundles $$A,B$$ such that neither $$A\succeq B$$ nor $$B \succeq A$$. Thus, it is not rational.
(ii) and (iii) are both rational. You can either see this by showing transitivity and completeness directly or you exploit a central result in microeconomics: A preference $$\succeq$$ can be represented by a utility function $$u$$ only if it is rational. For (ii), you can define $$u(x_1,x_2)=x_1$$ such that $$x_2$$ doesn't matter for comparisons as the preference states. For (iii), you can define Leontief preferences, $$u(x_1,x_2)=\min(x_1,x_2)$$.
For any two bundles either the first dimension differs, or the first one is equal and the second one differs or both are equal. So for any two bundles we have either $$\succeq$$ or $$\preceq$$ or both, i.e., the preferences are complete. They are also transitive because $$X\succeq Y$$ implies that either $$x_1>y_1$$ or $$x_1=y_1$$ and $$x_2\geq y_2$$ and $$Y\succeq Z$$ implies that either $$y_1>z_1$$ or $$y_1=z_1$$ and $$y_2\geq z_2$$. Therefore, either $$x_1>z_1$$ or $$x_1=z_1$$ and $$x_2\geq z_2$$, implying $$X\succeq Z$$.


text:
The square root of 24025 will have
Question:

The square root of 24025 will have________digits.

Solution:

3

Given number is 24025 .

Here, number of digits, $n=5$ (odd)

$\therefore$ Number of digits in the square root of $24025=\frac{n+1}{2}=\frac{5+1}{2}=3$


text:
# FAQ

Also relevant is the Troubleshooting, which goes over some (blocking) difficulties while launching.

Note

Please include the version in any bug reports or feature requests. The version number should look something like v0.4.1. It can be found at http://[url]:8421/docs or in the downloaded experiment file (found at http://[url]:8421/download which has a filename like exp-2021-05-20T07:31-salmon-v0.4.1.rdb).

## When should I use random/active sampling?

Rule of thumb:

• Use random sampling for simple problems when not many responses are required (small number of targets and clean responses).

• Use active sampling for anything more complicated (large number of targets or noisy responses) when the crowdsourcing budget and/or embedding quality are relevant.

Specifics are How many responses will be needed? and What active samplers are recommended?. Random sampling can produce good embeddings, but will require about 3× the number of responses that active sampling requires.

By default, Salmon will produce random embeddings. This is the simplest sampler, and doesn’t require any user configuration. Tips on how to use active samplers are in What active samplers are recommended?.

## How many responses will be needed?

Depends on the targets used, and how humans respond. Let’s say there are $$n$$ targets that are being embedded into $$d$$ dimensions. At most, we can provide bounds on how many responses you’ll need:

• Lower bound: at least $$nd\log_2(n)$$ responses are needed for a perfect embedding with noiseless responses. Active triplet algorithms require $$\Omega(nd\log_2(n))$$ responses (so a constant number of responses more/less). 1

• Upper bound: if random responses are collected, a high quality embedding will likely be generated with $$O(nd\log_2(n))$$ responses, likely $$20 nd \log_2(n)$$ responses (or possibly $$10 nd \log_2(n)$$). 2

This suggests that the number of responses required when $$n$$ and $$d$$ are changed scaled like $$nd\log_2(n)$$. i.e, if an embedding below requires 5,000 responses for $$n=30$$, scaling to $$n=40$$ with $$d=1$$ would likely require about $$3600 \approx 5000\frac{40 \cdot 1 \cdot \log_2(40)}{30\cdot 2 \cdot \log_2(30)}$$ responses for the same dataset.

See the benchmarks on active sampling for some benchmarks/landmarks on the specific number of responses required for a particular dataset. If you think your dataset will require too many responses, see our recommendations on active samplers. Active samplers might be able to generate better embeddings with a fixed number of responses.

## Can I choose a different machine?

All of our experiments are run with t3.xlarge instances. If you want to choose a different machine, ensure that is has the following:

• At least 4GB of RAM

• At least 3 CPU cores.

These are required because Salmon requires 3.2GB of memory and Dask has three tasks per adaptive algorithm: posting queries, searching queries, model updating. Generally, the number of cores should be 3 * n_algs. This isn’t a strict guideline; only 2 out of the 3 tasks take significant amounts of time. Using 2 * n_algs will work at a small performance hit; we recommend at least 4 cores for two algorithms.

## How do I ask specific questions?

It’s possible to configure what queries get shown to the crowdsourcing user with two methods:

1. By using Validation. You can specify a list of queries, or generate n_queries random queries. See Sampler configuration and the Validation sampler section.

2. By specifying the query key in Sampling’s detail field. This allows showing users specific queries at specific times. e.g., “for the first query the user sees, show them a query with [these objects].”

## How do I specify when samplers are used?

Controlling when or how often samplers get used is possible with two methods:

1. By setting the probs key in Sampling. If the YAML specifies sampling.probs: {"ARR": 80, "Random": 20}, the Random sampler will be used 20% of the time.

2. By setting the sampler field in Sampling’s detail field. This will ensure that the query is generated by a specific sampler (or which sampler will receive the answer if the query is pre-specified in your init.yaml per “How do I ask specific questions?”).

When sampling.probs is specified in your init.yaml, Salmon serves a query to a user with a certain probability. This can pose difficulties if you want to ask exactly $$N$$ questions to each crowdsourcing participant. Specifying sampling.details in your init.yaml will work around this and allow configuring the details of particular queries.

## How do I ask every crowdsourcing user exactly the same questions?

By specifying both the sampler key and the query key in Sampling’s detail field. The answers to the questions “How do I specify when samplers are used?” and “How do I ask specific questions?” are relevant.

An example is in “Sampling detail”, delegated to the Sampler configuration page because the target indexing in “Validation sampler” is relevant.

## How do I see the Dask dashboard?

Look at port 8787 if you want more information on how jobs are scheduled. If on EC2, this will require some port forwarding to your own machine:

ssh -i key.pem -L 7787:localhost:8787 [email protected][EC2 public DNS or IP]
# visit http://localhost:7787 in the browser to see Salmon's Dask dashboard

If desired, it is possible to open port 8787 on the Amazon EC2 machine. If that action is taken, it is recommended to only allow a specific IP to view that port.

## How do I customize the participant unique identifier aka “puid”?

Visiting http://[url]:8421/?puid=foobar will set that the participant UID to be foobar.

## How do I use HTTPS with Salmon?

HTTP is how web servers communicate; HTTPS protects that communication from third parties.

Some crowdsourcing services require HTTPS. There are to ways to provide these crowdsourcing services an HTTPS URL:

1. Redirect to Salmon from an HTTPS page.

2. Set up a TLS termination proxy.

Option (1) is a lot easier because various hosting services support HTTPS (e.g., GitHub Pages and GitLab Pages support HTTPS for custom domains). Hosting a redirect HTML page at one of these services with HTTPS will likely satisfy any requirements you may have.

Option (2) is more complex. A good overview is at FastAPI’s page “About HTTPS,” available at https://fastapi.tiangolo.com/deployment/https/. This process is beyond scope for this project. 3

1

“Low-dimensional embedding using adaptively selected ordinal data.” Jamieson and Nowak. 2011. Allerton Conference on Communication, Control, and Computing. https://homes.cs.washington.edu/~jamieson/resources/activeMDS.pdf

2

“Finite sample prediction and recovery bounds for ordinal embedding.” Jain, Jamieson and Nowak. 2016. NeurIPS. https://nowak.ece.wisc.edu/ordinal_embedding.pdf

3

though the package mkcert might help.

### The Docker machines aren’t launching

Are you using the command docker-compose up to launch Salmon? The command docker build . doesn’t work.

Salmon requires a Redis docker machine and certain directories/ports being available. Technically, it’s possible to build all the Docker machines yourself (but it’s not feasible).